I fumo 星（STL，数学）

链接：登录—专业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

输出

示例2

输入

输出

示例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;}