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
2
2
2
5
Author
LL
Source
题目大意：有n个指令，p加入一条线段,q查询id线段所在集合（两线段有交点为同一集合）的元素个数。
思路：用并查集路径压缩记录各个线段间的关系，根据叉积的定义有：Cross(v,w)=0时w在v上,>0时w在v上方,<0时w在v下方。
两线段有交点的必要条件：必须每条线段的两个端点在另一线段的两侧或直线上。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; const double eps=1e-;
const int maxn=;
int f[maxn];
struct Point
{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
};
struct Line
{
Point a,b;
}L[maxn];
typedef Point Vector;
Vector operator -(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
else return x<?-:;
}
double Cross(Vector A,Vector B){ return A.x*B.y-A.y*B.x;}//叉积 bool judge(Line a,Line b)//Cross(v,w)=0时w在v上,>0时w在v上方,<0时w在v下方
{
if(dcmp(Cross(a.a-b.a,b.b-b.a)*Cross(a.b-b.a,b.b-b.a))<=
&&dcmp(Cross(b.a-a.a,a.b-a.a)*Cross(b.b-a.a,a.b-a.a))<=)
return true;
return false;
}
int findset(int x){return f[x]!=x?f[x]=findset(f[x]):x;}
void Union(int a,int b)
{
a=findset(a);b=findset(b);
if(a!=b) f[a]=b;
}
int main()
{
int t,n,i,j,id;
char op[];
double x1,y1,x2,y2;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int cnt=;
for(i=;i<n;i++)
{
scanf("%s",op);
if(op[]=='P')
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
L[++cnt].a=Point(x1,y1);L[cnt].b=Point(x2,y2);
f[cnt]=cnt;
for(j=;j<=cnt-;j++)
if(judge(L[cnt],L[j]))
Union(j,cnt);
}
else
{
int ans=;scanf("%d",&id);
id=findset(id);
for(j=;j<=cnt;j++)
if(findset(j)==id)
ans++;
printf("%d\n",ans);
}
}
if(t) printf("\n");
}
return ;
}