Segment set |
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
Total Submission(s): 231 Accepted Submission(s): 104 |
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
HDU 2006-12 Programming Contest
|
Recommend
LL
|
/* 将有能通过某条线段连通的两条线段加入同一个并查集 */ #include<bits/stdc++.h> using namespace std; //点的结构体 struct point { double x,y; point(){} point(double a,double b) { x=a; y=b; } }; struct line { point a,b; line(){} line(point x,point y) { a=x; b=y; } }; int t,n; char op[2]; vector<line>v; //叉积 double cross(const point &a,const point &b,const point &o) { return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); } //判断两条直线是否相交,端点重合算相交 bool IsIntersect(const point &a,const point &b,const point &c,const point &d) { return ((cross(a,d,c)*cross(d,b,c)>=0)&&(cross(c,b,a)*cross(b,d,a)>=0)&&(max(c.x,d.x)>=min(a.x,b.x))&&(max(a.x,b.x)>=min(c.x,d.x))&&(max(c.y,d.y)>=min(a.y,b.y))&&(max(a.y,b.y)>=min(c.y,d.y))); } int bin[1010]; point x1,x2; void inti() { for(int i=0;i<=n;i++) bin[i]=i; } int findx(int x) { while(x!=bin[x]) x=bin[x]; return x; } int main() { //freopen("C:\Users\acer\Desktop\in.txt","r",stdin); scanf("%d",&t); for(int ca=1;ca<=t;ca++) { if(ca!=1) printf(" "); //for(int i=0;i<=n;i++) // cout<<bin[i]<<" "; //cout<<endl; scanf("%d",&n); v.clear(); inti(); while(n--) { scanf("%s",op); if(op[0]=='P')//添加边 { scanf("%lf%lf%lf%lf",&x1.x,&x1.y,&x2.x,&x2.y); v.push_back(line(x1,x2)); int cur=v.size(); line temp=v[cur-1]; for(int i=1;i<v.size();i++) { if(IsIntersect(temp.a,temp.b,v[i-1].a,v[i-1].b))//两条线段有交点 { //cout<<"i="<<i<<" cur="<<cur<<endl; int fx=findx(i); int fy=findx(cur); //for(int i=0;i<=n;i++) // cout<<bin[i]<<" "; //cout<<endl; if(fx!=fy) bin[fx]=fy; } } } else//询问与那条边关联 { int q; int cnt=0; scanf("%d",&q); for(int i=1;i<=v.size();i++) { int fx=findx(i); int fy=findx(q); //cout<<"fx="<<fx<<" fy="<<fy<<endl; if(fx==fy) { //cout<<"i="<<i<<" q="<<q<<endl; cnt++; } } printf("%d ",cnt); } } } return 0; }