链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
假设平面上有 nnn 颗 fumo 星，编号分别为 1,2,…,n1,2,\dots,n1,2,…,n。求这样的直线的数量：直线经过这 nnn 颗 fumo 星中至少 222 个序号不同的 fumo 星。
输入描述:
首先输入一行一个整数 n(1≤n≤103)n(1\leq n \leq 10^{3})n(1≤n≤103)，表示 fumo 星的数量。
接下来输入 n 行，每行 2 个整数 xi,yi(−109≤xi≤109,−109≤yi≤109)代表序号为 i 的 fumo 星的横坐标与纵坐标。
输出描述:
如果有无数条满足的直线，输出 "inf"（不含引号）；否则输出一行一个整数，表示直线的数量。
示例1
输入
2 1 1 2 2
输出
1
示例2
输入
4 0 0 1 1 2 2 3 3
输出
1
示例3
输入
2 1 1 1 1
输出
inf
解析：
看完题目，先别急着做题，先看数据范围，再看时间限制。发现时间限制很大，我们可以使用n^2级别的时间复杂度来处理这个问题。
最简单的方法就是将所有的点都遍历一遍，每次遍历的时候枚举所有可能与它形成直线的点。同时使用gcd将斜率化成最小分数，使用map或其他容器存储每个点形成的所有直线。
根据初中知识，确定一条直线只需要一个点和一个斜率即可。
因此可以这样存一条直线：map<点，map<斜率，是否存在>>mp;
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef pair<double, double> PDD;
const int INF = 0x3f3f3f3f;
const LL Mod = 1e9;
const int N = 1e3 + 10, M = 4e5 + 10, P = 110;
int n;
struct node {
int x, y;
}node[N];
map<int, map<pair<int,int>, int>>mp;
map<PII, int>p;
int gcd(int a, int b) {
if (b == 0)return a;
return gcd(b, a % b);
}
int main() {
cin >> n;
int flg = 0;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &node[i].x, &node[i].y);
if (p.count({ node[i].x,node[i].y })) {
flg = 1;
}
p[{node[i].x,node[i].y}]=1;
}
int ans = 0;
if (flg) {
cout << "inf" << endl;
}
else {
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
int x = node[i].x - node[j].x, y = node[i].y - node[j].y;
int g = gcd(x, y);
x /= g;
y /= g;
if (!mp[j].count({x,y})) {
ans++;
}
mp[j][{x,y}] = 1;
mp[i][{x, y}] = 1;
}
}
cout << ans << endl;
}
return 0;
}
再提供一个队友写的代码，效率更高：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
const int N = 1e4 + 10;
#define LL long long
tuple<LL, LL, LL> o;
set<tuple<LL, LL, LL> > p;
LL a[N], b[N];
LL n;
LL gcd(LL x, LL y)
{
if (!y) return x;
return gcd(y, x % y);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
if (n == 1)
{
cout << 0 << endl;
return 0;
}
int flag = 0;
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (a[i] == a[j] && b[i] == b[j])
{
flag = 1;
break;
}
LL x = b[j] - b[i], y = a[j] - a[i], z = y * b[i] - x * a[i];
LL gc = gcd(gcd(x, y), z);
if (!gc) p.insert({ x,y,z });
else {
x = x / gc;
y /= gc;
z /= gc;
p.insert({ x,y,z });
}
}
if (flag)
break;
}
if (flag)
{
cout << "inf" << endl;
return 0;
}
cout << p.size() << endl;
return 0;
}
