Segment setTime Limit: 3000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3907Accepted Submission(s): 1471
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
110P 1.00 1.00 4.00 2.00P 1.00 -2.00 8.00 4.00Q 1P 2.00 3.00 3.00 1.00Q 1Q 3P 1.00 4.00 8.00 2.00Q 2P 3.00 3.00 6.00 -2.00Q 5
Sample Output
12225
Author
LL
题目大意：在一个平面直角坐标系里面，通过P操作不断的加入线段，如果两个线段有相交，，就表明他们是一个集合里面的。Q操作询问当前情况下第k条线段所在的集合里面有几条线段。
并查集的题目，但是我觉得主要考几何。我开始可以想到，通过判断两条线段是否有交点，如果有就放在一个集合里面。这么想的确很简单，但是做起来真的十分麻烦。。
如果对于两条线段，可以通过简单计算得到两者的交点x0=(b2-b1)/(k1-k2)，还有y0。那么我只要判断x0,y0是否在线段相交的地方即可。但是还要注意，这个交点是从k1,k2得到的。所以如果k1,k2不存在，又要分情况讨论。
以下是我的代码，感觉好像还有遗漏的地方，虽然的确是AC了。
#include<stdio.h>#include<string.h>int p[10000],sum[10000];double x1[1005],x2[1005],y1[1005],y2[1005];void init(int x){int i;for(i=0;i<=x;i++)p[i]=i;for(i=0;i<=x;i++)sum[i]=1;}int findroot(int x){int r=x;while(r!=p[r])r=p[r];int i,j;i=x;while(i!=r){j=p[i];p[i]=r;i=j;}return r;}void merge(int x,int y){int fx=findroot(x);int fy=findroot(y);if(fx!=fy){p[fx]=fy;sum[fy]+=sum[fx];}}double jiaodian(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4){if(x1==x2&&x3!=x4){//k1不存在,k2存在double k2=(y3-y4)/(x3-x4);double y=k2*(x1-x3)+y3;if((y>=y1&&y<=y2)||(y>=y2&&y<=y1))return 1;else return 0;} else if(x3==x4&&x1!=x2){//k2不存在，k1存在double k1=(y1-y2)/(x1-x2);double y=k1*(x3-x1)+y1;if((y>=y3&&y<=y4)||(y>=y4&&y<=y3))return 1;else return 0;} else if(x1==x2&&x3==x4){if(x1==x3&&((y1>=y3&&y1<=y4)||(y1>=y4&&y1<=y3)||(y2>=y4&&y2<=y3)||(y2>=y3&&y2<=y4)))return 1;else return 0;}double k1=(y1-y2)/(x1-x2);double k2=(y3-y4)/(x3-x4);double b1=(x1*y2-x2*y1)/(x1-x2);double b2=(x3*y4-x4*y3)/(x3-x4);double x=(b2-b1)/(k1-k2);double y=k1*(x-x1)+y1;if(((x>=x1&&x<=x2)||(x>=x2&&x<=x1))&&((y>=y1&&y<=y2)||(y>=y2&&y<=y1))&&((x>=x3&&x<=x4)||(x>=x4&&x<=x3))||((y>=y3&&y<=y4)&&(y>=y4&&y<=y3)))return 1;return 0;}void isconnect(int x){int i;for(i=1;i<=x;i++) {if(jiaodian(x1[i],y1[i],x2[i],y2[i],x1[x],y1[x],x2[x],y2[x])){merge(i,x);} } return ;}int main(){int t,n,i,j,k,m,cnt,q;char c[10];scanf("%d",&t);while(t–){q=1;scanf("%d",&n);init(n);cnt=1;for(i=1;i<=n;i++){scanf("%s",c);if(c[0]=='P'){scanf("%lf%lf%lf%lf",&x1[q],&y1[q],&x2[q],&y2[q]);if(i>1){isconnect(q);}q++;}if(c[0]=='Q'){scanf("%d",&k);int s=findroot(k);cnt=sum[s];printf("%d\n",cnt);}}if(t>0)printf("\n");}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上帝从不埋怨人们的愚昧，人们却埋怨上帝的不公
