1 #include <iostream>  2 #include <cmath>  3 #include <cstring>  4 #include <cstdio>  5 using namespace std;  6   7 int f[1010];  8 char ch;  9 int tmp,n; 10 double X1,X2,Y1,Y2; 11  12    #define eps 1e-8 13    #define PI acos(-1.0)//3.14159265358979323846 14    //判断一个数是否为0,是则返回true,否则返回false 15    #define zero(x)(((x)>0?(x):-(x))<eps) 16    //返回一个数的符号，正数返回1，负数返回2，否则返回0 17    #define _sign(x)((x)>eps?1:((x)<-eps?2:0)) 18   struct point 19   { 20       double x,y; 21       point(){} 22       point(double xx,double yy):x(xx),y(yy) 23       {} 24   }; 25   struct line 26   { 27       point a,b; 28       line(){}      //默认构造函数 29       line(point ax,point bx):a(ax),b(bx) 30       {} 31   }l[1010];//直线通过的两个点，而不是一般式的三个系数 32  33    //求矢量[p0,p1],[p0,p2]的叉积 34    //p0是顶点 35    //若结果等于0，则这三点共线 36    //若结果大于0，则p0p2在p0p1的逆时针方向 37    //若结果小于0，则p0p2在p0p1的顺时针方向 38    double xmult(point p1,point p2,point p0) 39    { 40        return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 41    } 42    //计算dotproduct(P1-P0).(P2-P0) 43    double dmult(point p1,point p2,point p0) 44    { 45        return(p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y); 46    } 47    //两点距离 48    double distance(point p1,point p2) 49    { 50        return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); 51    } 52    //判三点共线 53    int dots_inline(point p1,point p2,point p3) 54    { 55        return zero(xmult(p1,p2,p3)); 56    } 57    //判点是否在线段上,包括端点 58    int dot_online_in(point p,line l) 59    { 60        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; 61    } 62    //判点是否在线段上,不包括端点 63    int dot_online_ex(point p,line l) 64    { 65        return dot_online_in(p,l)&&(!zero(p.x-l.a.x)||!zero(p.y-l.a.y))&&(!zero(p.x-l.b.x)||!zero(p.y-l.b.y)); 66    } 67    //判两点在线段同侧,点在线段上返回0 68    int same_side(point p1,point p2,line l) 69    { 70        return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps; 71    } 72    //判两点在线段异侧,点在线段上返回0 73    int opposite_side(point p1,point p2,line l) 74    { 75        return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)<-eps; 76    } 77    //判两直线平行 78    int parallel(line u,line v) 79    { 80        return zero((u.a.x-u.b.x)*(v.a.y-v.b.y)-(v.a.x-v.b.x)*(u.a.y-u.b.y)); 81    } 82    //判两直线垂直 83    int perpendicular(line u,line v) 84    { 85        return zero((u.a.x-u.b.x)*(v.a.x-v.b.x)+(u.a.y-u.b.y)*(v.a.y-v.b.y)); 86    } 87    //判两线段相交,包括端点和部分重合 88    int intersect_in(line u,line v) 89    { 90        if(!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b)) 91            return!same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u); 92        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); 93    } 94 int find(int x) 95 { 96     if (f[x]!=x) 97         f[x]=find(f[x]); 98     return f[x]; 99 }100 101 void iunion(int x,int y)102 {103     int fx,fy;104     fx=find(x);105     fy=find(y);106     if (fx!=fy)107         f[fx]=fy;108 }109 110 int main()111 {112     //freopen("in.txt","r",stdin);113     int times;114     cin>>times;115     while(times--)116     {117 118     cin>>n;119     int T=0;120     for (int i=1;i<=n;i++)121     {122         /*123         cout<<"dev: ";124         for (int j=1;j<=T;j++)125             cout<<f[j]<<" ";126         cout<<endl;127         */128         cin>>ch;129         if (ch==‘Q‘)130         {131             cin>>tmp;132             int ans=0;133             for (int j=1;j<=T;j++)134                 if (find(tmp)==find(j))     ans++;135             cout<<ans<<endl;136         }137         else if (ch==‘P‘)138         {139             cin>>X1>>Y1>>X2>>Y2;140             T++;141             f[T]=T;142             l[T]=line(point(X1,Y1),point(X2,Y2));143             //cout<<l[T].a.x<<" "<<l[T].a.y<<" "<<l[T].b.x<<" "<<l[T].b.y<<endl;144             for (int j=1;j<T;j++)145                 if (intersect_in(l[T],l[j])>0)146                     iunion(j,T);147         }148     }149 150     if (times>0)151         cout<<endl;152     }153     return 0;154 }