SYZOJ-236-小L的直线(卡小数精度)

发布于 2019-08-14  425 次阅读


问题传送门:

题意:

给出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;
}

Simple And Clear