1 /* 1558 */  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5   6 #define MAXN 1005  7   8 typedef struct {  9     double x, y; 10 } Point_t; 11  12 typedef struct { 13     Point_t b, e; 14 } Seg_t; 15  16 Seg_t segs[MAXN]; 17 int pre[MAXN]; 18 int ans[MAXN]; 19  20 int max(int a, int b) { 21     return a>b ? a:b; 22 } 23  24 int min(int a, int b) { 25     return a<b ? a:b; 26 } 27  28 double direction(Point_t p0, Point_t p1, Point_t p2) { 29     return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x); 30 } 31  32 bool onSegment(Point_t p0, Point_t p1, Point_t p2) { 33     if ( (min(p0.x, p1.x)<=p2.x && p2.x<=max(p0.x, p1.x)) && 34          (min(p0.y, p1.y)<=p2.y && p2.y<=max(p0.y, p1.y)) ) 35         return true; 36     return false; 37 } 38  39 bool intersect(Seg_t x, Seg_t y) { 40     Point_t p1 = x.b, p2 = x.e, p3 = y.b, p4 = y.e; 41     double d1 = direction(p3, p4, p1); 42     double d2 = direction(p3, p4, p2); 43     double d3 = direction(p1, p2, p3); 44     double d4 = direction(p1, p2, p4); 45     if ( ((d1>0 && d2<0) || (d1<0 && d2>0)) && 46          ((d3>0 && d4<0) || (d3<0 && d4>0)) ) 47         return true; 48     else if (d1==0 && onSegment(p3, p4, p1)) 49         return true; 50     else if (d2==0 && onSegment(p3, p4, p2)) 51         return true; 52     else if (d3==0 && onSegment(p1, p2, p3)) 53         return true; 54     else if (d4==0 && onSegment(p1, p2, p4)) 55         return true; 56     else 57         return false; 58 } 59  60 int find(int x) { 61     if (x == pre[x]) 62         return x; 63     pre[x] = find(pre[x]); 64     return pre[x]; 65 } 66  67 void merge(int x, int y) { 68     int fx = find(x); 69     int fy = find(y); 70     if (fx != fy) { 71         pre[fy] = fx; 72         ans[fx] += ans[fy]; 73         ans[fy] = 0; 74     } 75 } 76  77 int main() { 78     int t, n, m; 79     int i, j, k; 80     char cmd[3]; 81      82     #ifndef ONLINE_JUDGE 83         freopen("data.in", "r", stdin); 84     #endif 85      86     scanf("%d", &t); 87     while (t--) { 88         scanf("%d", &n); 89         for (i=1; i<=n; ++i) { 90             pre[i] = i; 91             ans[i] = 1; 92         } 93         m = 1; 94         while (n--) { 95             scanf("%s", cmd); 96             if (cmd[0] == ‘P‘) { 97                 scanf("%lf%lf%lf%lf", &segs[m].b.x, &segs[m].b.y, &segs[m].e.x, &segs[m].e.y); 98                 for (i=1; i<m; ++i) { 99                     if (intersect(segs[i], segs[m]))100                         merge(i, m);101                 }102                 ++m;103             } else {104                 scanf("%d", &j);105                 k = find(j);106                 printf("%d\n", ans[k]);107             }108         }109         if (t)110             printf("\n");111     }112     113     return 0;114 }