题意:
给出n个点的坐标,问最多能画出几条直线,使得不出现平行的线。(n <= 200)
分析:
只有200个点的话,直接求出所有可能的斜率,
把重复的除去,剩下多少个斜率就是答案。
然而,直接算斜率的话会有小数精度的问题,
那就不用小数,直接用分数来表示斜率。
pair<int, int> , first是分子,second是分母。
代码:
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 300;
struct Node
{
int x, y;
} a[MAXN];
typedef pair<int, int> P;
set<P> S;
int main()
{
int n, t1, t2, g;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i].x >> a[i].y;
for (int i = 0; i < n-1; i++)
{
for (int j = i+1; j < n; j++)
{
if (a[i].x==a[j].x && a[i].y==a[j].y)
continue;
t2=a[i].y-a[j].y, t1=a[i].x-a[j].x;
g = __gcd(t1, t2);
t1 /= g, t2 /= g;
S.insert(P(t2, t1));
}
}
cout << S.size() << endl;
return 0;
}
Comments | NOTHING