题解 P2665 【[USACO08FEB]连线游戏Game of Lines】

大头 · 2017-02-09 09:59:39 · 题解

水题一道。

对斜率进行排序，判重即可。

注意：特判一下直线与坐标轴垂直的情况。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm> 
using namespace std;
double a[205],b[205],c[40005];
int n,ans,cnt;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i],&b[i]);
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++)
            if (a[i]==a[j]) c[++cnt]=0;
            else if (b[i]==b[j]) c[++cnt]=10000;
            else c[++cnt]=(a[i]-a[j])/(b[i]-b[j]);
    sort(c+1,c+cnt+1);
    ans=1;
    for (int i=2;i<=cnt;i++)
        if (c[i]-c[i-1]>1e-10) ans++;
    printf("%d",ans);
}