Jack Straws 线段相交加并查集

/*开始的时候并查集写错了。就是有传递闭包的关系。不错的一个题。*/#include <stdio.h>#define eps 1e-8double max(double a,double b){    if(b-a<-eps) return a;    else return b;}double min(double a,double b){    if(b-a<-eps) return b;    else return a;}struct point{    double x,y;};struct LINE{    point p1,p2;}line[14];int f[14];double multi(point p0,point p1,point p2){    return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));}bool cross(LINE a,LINE b){    if(min(a.p1.x,a.p2.x)-max(b.p1.x,b.p2.x)<eps            &&min(a.p1.y,a.p2.y)-max(b.p1.y,b.p2.y)<eps            &&min(b.p1.x,b.p2.x)-max(a.p1.x,a.p2.x)<eps            &&min(b.p1.y,b.p2.y)-max(a.p1.y,a.p2.y)<eps            &&multi(a.p1,a.p2,b.p1)*multi(a.p1,a.p2,b.p2)<=eps            &&multi(b.p1,b.p2,a.p1)*multi(b.p1,b.p2,a.p2)<=eps)        return true;    else return false;}int find(int x){    if(x!=f[x])        f[x]=find(f[x]);    return f[x];}void unit(int x,int y){    x=find(x);    y=find(y);    if(x==y) return ;    else f[y]=x;}int main(){    int n,r,t;    while(scanf("%d",&n)==1&&n)    {        for(int i=1; i<=n; i++)            f[i]=i;        for(int i=1; i<=n; i++)            scanf("%lf%lf%lf%lf",&line[i].p1.x,&line[i].p1.y,&line[i].p2.x,&line[i].p2.y);        for(int i=1; i<=n; i++)            for(int j=i+1; j<=n; j++)            {                if(cross(line[i],line[j]))                    unit(i,j);            }        while(scanf("%d%d",&r,&t)==2)        {            if(r==0&&t==0) break;            if(find(r)==find(t))                printf("CONNECTED\n");            else printf("NOT CONNECTED\n");        }    }    return 0;}