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