Segment set
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3474 Accepted Submission(s): 1295
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.
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
//hdoj 1558 并查集加计算几何
#include<iostream>
#include<stdio.h>
using namespace std;
struct point{
double x,y;
};
struct bian{
point a,b;
};
bian edge[1001];
int E;
int pre[1001],sum[1001];
int find(int x)
{
if(x==pre[x]) return x;
else pre[x]=find(pre[x]);
return pre[x];
}
void merge(int a,int b)
{
int x,y;
x=find(a);
y=find(b);
if(x!=y)
{
pre[x]=y;
sum[y]+=sum[x];
}
}
//计算几何部分 线段相交的内容参考算法导论P577
double xmult(point a,point b,point c)//大于零代表a,b,c左转
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool OnSegment(point a,point b,point c)//a,b,c共线时有效
{
return c.x>=min(a.x,b.x)&&c.x<=max(a.x,b.x)&&c.y>=min(a.y,b.y)&&c.y<=max(a.y,b.y);
}
bool cross(point a,point b,point c,point d){//判断ab 与cd是否相交
double d1,d2,d3,d4;
d1=xmult(c,d,a);
d2=xmult(c,d,b);
d3=xmult(a,b,c);
d4=xmult(a,b,d);
if(d1*d2<0&&d3*d4<0) return 1;
else if(d1==0&&OnSegment(c,d,a)) return 1;
else if(d2==0&&OnSegment(c,d,b)) return 1;
else if(d3==0&&OnSegment(a,b,c)) return 1;
else if(d4==0&&OnSegment(a,b,d)) return 1;
return 0;
}
int main()
{
int T,n,i,j,k;
char str[3];
// freopen("test.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
E=0;
for(i=1;i<=n;i++)
pre[i]=i,sum[i]=1;
for(i=1;i<=n;i++)
{
scanf("%s",str);
if(str[0]=='P')
{
E++;
scanf("%lf%lf%lf%lf",&edge[E].a.x,&edge[E].a.y,&edge[E].b.x,&edge[E].b.y);
for(j=1;j<E;j++)
if(find(E)!=find(j)&&cross(edge[E].a,edge[E].b,edge[j].a,edge[j].b))
merge(E,j);
}
else if(str[0]=='Q')
{
scanf("%d",&k);
printf("%d\n",sum[find(k)]);
}
}
if(T!=0) printf("\n");
}
return 0;
}