POJ 1127 Jack Straws

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cmath>
  5 #define MAX_N 15
  6 
  7 using namespace std;
  8 
  9 double EPS=1e-10;
 10 
 11 double add(double a,double b)
 12 {
 13     if(fabs(a+b)<EPS*(fabs(a)+fabs(b)))
 14         return 0;
 15     return a+b;
 16 }
 17 
 18 struct P
 19 {
 20     double x,y;
 21 
 22     P(){}
 23 
 24     P(double x,double y):x(x),y(y){}
 25 
 26     P operator + (P p)
 27     {
 28         return P(add(x,p.x),add(y,p.y));
 29     }
 30 
 31     P operator - (P p)
 32     {
 33         return P(add(x,-p.x),add(y,-p.y));
 34     }
 35 
 36     P operator * (double d)
 37     {
 38         return P(x*d,y*d);
 39     }
 40 
 41     //内积
 42     double dot(P p)
 43     {
 44         return add(x*p.x,y*p.y);
 45     }
 46 
 47     //外积
 48     double det(P p)
 49     {
 50         return add(x*p.y,-y*p.x);
 51     }
 52 };
 53 
 54 //判断点q是否在线段p1-p2上
 55 bool on_seg(P p1,P p2,P q)
 56 {
 57     return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;
 58 }
 59 
 60 //计算直线p1-p2与直线q1-q2的交点
 61 P intersection(P p1,P p2,P q1,P q2)
 62 {
 63     return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
 64 }
 65 
 66 int n;
 67 P p[MAX_N],q[MAX_N];
 68 bool g[MAX_N][MAX_N];
 69 
 70 void solve()
 71 {
 72     for(int i=0;i<n;i++)
 73     {
 74         g[i][i]=true;
 75         for(int j=0;j<i;j++)
 76         {
 77             //判断木棍i和木棍j是否有公共点
 78             if((p[i]-q[i]).det(p[j]-q[j])==0)
 79             {
 80                 //平行时，判断是否可能在端点处有交点
 81                 g[i][j]=g[j][i]=on_seg(p[i],q[i],p[j])||on_seg(p[i],q[i],q[j])||on_seg(p[j],q[j],p[i])||on_seg(p[j],q[j],q[i]);
 82             }
 83             else
 84             {
 85                 //非平行时，先求出两直线交点再凑数交点是否在两条线段上
 86                 P r=intersection(p[i],q[i],p[j],q[j]);
 87                 g[i][j]=g[j][i]=on_seg(p[i],q[i],r)&&on_seg(p[j],q[j],r);
 88             }
 89         }
 90     }
 91 
 92     //通过Floyd-Warshall算法判断任意的两点间是否相连
 93     for(int k=0;k<n;k++)
 94         for(int i=0;i<n;i++)
 95             for(int j=0;j<n;j++)
 96                 g[i][j]|=g[i][k]&&g[k][j];
 97 }
 98 
 99 int main()
100 {
101     while(scanf("%d",&n)&&n)
102     {
103         for(int i=0;i<n;i++)
104             scanf("%lf %lf %lf %lf",&p[i].x,&p[i].y,&q[i].x,&q[i].y);
105         solve();
106         int a,b;
107         while(scanf("%d %d",&a,&b)&&(a||b))
108             puts(g[a-1][b-1]?"CONNECTED":"NOT CONNECTED");
109     }
110 
111     return 0;
112 }