周赛 直线重合 题解(用分数代替小数完全避免浮点误差)

题目链接

题目思路

本来是用浮点数写，但是发现浮点数一定有浮点误差，学长卡死了double ，这时必须换一个思路。其实k,b可以用分数储存，

那么可以完美的避免避免浮点误差。

注意：

1：本来我以为会出现 1/-2！=-1/2 的情况，后面仔细一想发现不可能，以为假设分子为1分母为-2，分子为-1，分母为2的两组数。

他们的gcd也会相反所以除以gcd之后又相等了。

2：还有排序要注意要所有元素都排序，不要只考虑一个元素（wa了几发）

3：注意斜率不存在要分开讨论

代码

#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=1e5+5;
int n,a,b,c,d;
struct node{
    int kx,ky,bx,by,prime;//prime用来标记k是不是不存在
}e[maxn];
int gcd(int x,int y){//找最大公约数
    if(y==0)
        return x;
    return gcd(y,x%y);
}
bool cmp(node a,node b){//排序为了去重
    if(a.kx!=b.kx){
        return a.kx<b.kx;
    }else if(a.ky!=b.ky){
        return a.ky<b.ky;
    }else if(a.bx!=b.bx){
        return a.bx<b.bx;
    }else if(a.by!=b.by){
        return a.by<b.by;
    }else{
        return a.prime<b.prime;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(a==c){//分母为0特殊处理
            e[i].prime=1;
            e[i].kx=a;//只要标记x=a;即可
        }else{
            int yu1=gcd(c-a,d-b);
            e[i].ky=(d-b)/yu1;
            e[i].kx=(c-a)/yu1;
            int yu2=gcd(d*e[i].kx-c*e[i].ky,e[i].kx);//b=(d*kx-c*ky)/kx
            e[i].by=(d*e[i].kx-c*e[i].ky)/yu2;
            e[i].bx=e[i].kx/yu2;
        }
    }
    sort(e+1,e+1+n,cmp);
    int ans=n;
    for(int i=1;i<n;i++){//去重
        if(e[i].kx==e[i+1].kx&&e[i].ky==e[i+1].ky&&e[i].bx==e[i+1].bx&&e[i].by==e[i+1].by&&e[i].prime==e[i+1].prime){
            ans--;
        }
    }
    printf("%d",ans);
    return 0;
}