抄的模版，居然1Y了。就是简单的线段相交+并查集。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 using namespace std; 7 #define eps 1e-8 8 #define zero(x) (((x) > 0?(x):(-x))<eps) 9 10 struct point 11 { 12 double x,y; 13 }; 14 struct line 15 { 16 point a,b; 17 }; 18 int o[100]; 19 line p[101]; 20 int xmult(point p1,point p2,point p0) 21 { 22 return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x); 23 } 24 int dot_online_in(point p,line l) 25 { 26 return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x) < eps&&(l.a.y-p.y)*(l.b.y-p.y) < eps; 27 } 28 int dots_online(point p1,point p2,point p3) 29 { 30 return zero(xmult(p1,p2,p3)); 31 } 32 int same_side(point p1,point p2,line l) 33 { 34 return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b) > eps; 35 } 36 int interset_in(line u,line v) 37 { 38 if(!dots_online(u.a,u.b,v.a)||!dots_online(u.a,u.b,v.b)) 39 return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u); 40 41 return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u); 42 } 43 int find(int x) 44 { 45 while(x != o[x]) 46 x = o[x]; 47 return x; 48 } 49 void merge(int x,int y) 50 { 51 x = find(x); 52 y = find(y); 53 if(x != y) 54 o[x] = y; 55 } 56 int main() 57 { 58 int n,i,j,x,y; 59 60 while(scanf("%d",&n)!=EOF) 61 { 62 if(n == 0) break; 63 for(i = 1;i <= n;i ++) 64 { 65 o[i] = i; 66 scanf("%lf%lf%lf%lf",&p[i].a.x,&p[i].a.y,&p[i].b.x,&p[i].b.y); 67 } 68 for(i = 1;i <= n;i ++) 69 { 70 for(j = i+1;j <= n;j ++) 71 { 72 if(interset_in(p[i],p[j])) 73 merge(i,j); 74 } 75 } 76 for(;;) 77 { 78 scanf("%d%d",&x,&y); 79 if(x == 0&&y == 0) break; 80 if(find(x) == find(y)) 81 printf("CONNECTED "); 82 else 83 printf("NOT CONNECTED "); 84 } 85 } 86 87 return 0; 88 }