|
蓝桥杯算法训练-共线
一颗小码农:
我刚开始也是你这种做法，但是把hashmap移到第一层for循环外面了，导致重复计算了好多点。感觉可以用k1,k2的形式来避免两个double相除造成的精度损失问题。不过你这样的好处也省去了，求最大公约数的麻烦，更方便[code=cpp]
#include
#include
using namespace std;
int lcd(int x, int y)
{
return y ? lcd(y, x % y) : x;
}
const int N = 1e4;
pair a[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
scanf("%d%d", &a[i].first, &a[i].second);
}
int res = 0;
for (int i = 0; i < n; ++i)
{
mapm;
for (int j = i + 1; j < n; ++j)
{
int k1 = a[i].first - a[j].first;
int k2 = a[i].second - a[j].second;
//获得最大公约数
int c = lcd(k1, k2);
k1 /= c;
k2 /= c;
pairp;
p.first = k1;
p.second = k2;
if (m[p] == 0)
++m[p];
++m[p];
res = max(res, m[p]);
}
}
cout |