Segment set

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3457    Accepted Submission(s): 1290

Problem Description

A segment and all segments which are connected with it compose a segment set. The size of a segment set is the number of segments in it. The problem is to find the size of some segment set.

 

 

Input

In the first line there is an integer t - the number of test case. For each test case in first line there is an integer n (n<=1000) - the number of commands. 

There are two different commands described in different format shown below:

P x1 y1 x2 y2 - paint a segment whose coordinates of the two endpoints are (x1,y1),(x2,y2).

Q k - query the size of the segment set which contains the k-th segment.

k is between 1 and the number of segments in the moment. There is no segment in the plane at first, so the first command is always a P-command.

 

 

Output

For each Q-command, output the answer. There is a blank line between test cases.

 

 

Sample Input

1

10

P 1.00 1.00 4.00 2.00

P 1.00 -2.00 8.00 4.00

Q 1

P 2.00 3.00 3.00 1.00

Q 1

Q 3

P 1.00 4.00 8.00 2.00

Q 2

P 3.00 3.00 6.00 -2.00

Q 5

 

 

Sample Output

1 2 2 2 5

 

 

Author

LL

 

 

Source

 

题目大意：有n个指令，p加入一条线段,q查询id线段所在集合（两线段有交点为同一集合）的元素个数。

思路：用并查集路径压缩记录各个线段间的关系，根据叉积的定义有：Cross(v,w)=0时w在v上,>0时w在v上方,<0时w在v下方。

两线段有交点的必要条件：必须每条线段的两个端点在另一线段的两侧或直线上。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 const double eps=1e-8; 8 const int maxn=1005; 9 int f[maxn];10 struct Point11 {12     double x,y;13     Point(){}14     Point(double x,double y):x(x),y(y){}15 };16 struct Line17 {18     Point a,b;19 }L[maxn];20 typedef Point Vector;21 Vector operator -(Vector A,Vector B){
    return Vector(A.x-B.x,A.y-B.y);}22 int dcmp(double x)23 {24     if(fabs(x)
          
           0时w在v上方,<0时w在v下方30 {31     if(dcmp(Cross(a.a-b.a,b.b-b.a)*Cross(a.b-b.a,b.b-b.a))<=032         &&dcmp(Cross(b.a-a.a,a.b-a.a)*Cross(b.b-a.a,a.b-a.a))<=0)33         return true;34     return false;35 }36 int findset(int x){
    return f[x]!=x?f[x]=findset(f[x]):x;}37 void Union(int a,int b)38 {39     a=findset(a);b=findset(b);40     if(a!=b) f[a]=b;41 }42 int main()43 {44     int t,n,i,j,id;45     char op[5];46     double x1,y1,x2,y2;47     scanf("%d",&t);48     while(t--)49     {50         scanf("%d",&n);51         int cnt=0;52         for(i=0;i