并查集+计算几何。
/* 1558 */
#include <cstdio>
#include <cstring>
#include <cstdlib> #define MAXN 1005 typedef struct {
double x, y;
} Point_t; typedef struct {
Point_t b, e;
} Seg_t; Seg_t segs[MAXN];
int pre[MAXN];
int ans[MAXN]; int max(int a, int b) {
return a>b ? a:b;
} int min(int a, int b) {
return a<b ? a:b;
} double direction(Point_t p0, Point_t p1, Point_t p2) {
return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x);
} bool onSegment(Point_t p0, Point_t p1, Point_t p2) {
if ( (min(p0.x, p1.x)<=p2.x && p2.x<=max(p0.x, p1.x)) &&\
(min(p0.y, p1.y)<=p2.y && p2.y<=max(p0.y, p1.y)) )
return true;
return false;
} bool intersect(Seg_t x, Seg_t y) {
Point_t p1 = x.b, p2 = x.e, p3 = y.b, p4 = y.e;
double d1 = direction(p3, p4, p1);
double d2 = direction(p3, p4, p2);
double d3 = direction(p1, p2, p3);
double d4 = direction(p1, p2, p4);
if ( ((d1> && d2<) || (d1< && d2>)) &&\
((d3> && d4<) || (d3< && d4>)) )
return true;
else if (d1== && onSegment(p3, p4, p1))
return true;
else if (d2== && onSegment(p3, p4, p2))
return true;
else if (d3== && onSegment(p1, p2, p3))
return true;
else if (d4== && onSegment(p1, p2, p4))
return true;
else
return false;
} int find(int x) {
if (x == pre[x])
return x;
pre[x] = find(pre[x]);
return pre[x];
} void merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
pre[fy] = fx;
ans[fx] += ans[fy];
ans[fy] = ;
}
} int main() {
int t, n, m;
int i, j, k;
char cmd[]; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (i=; i<=n; ++i) {
pre[i] = i;
ans[i] = ;
}
m = ;
while (n--) {
scanf("%s", cmd);
if (cmd[] == 'P') {
scanf("%lf%lf%lf%lf", &segs[m].b.x, &segs[m].b.y, &segs[m].e.x, &segs[m].e.y);
for (i=; i<m; ++i) {
if (intersect(segs[i], segs[m]))
merge(i, m);
}
++m;
} else {
scanf("%d", &j);
k = find(j);
printf("%d\n", ans[k]);
}
}
if (t)
printf("\n");
} return ;
}