本文共 2953 字，大约阅读时间需要 9 分钟。
用到的计算几何中的内容至今不大懂，目前练习并查集，以后待续、、、、
1、题目大意：
给你一些操作，P后边输入四个值，分别代表一条线段的起点、终点坐标，
当输入Q时，后边输入一个整形值K，输出第k条线段所在的集合中包含的线段的个数
2、思路：用并查集做
当输入P时，判断后边输入的线段的起点和终点时，判断跟之前的线段有没有相交，如果有相交，就merge（）合并，
如果输入的是Q时，就打印出当前线段所在集合的个数
3、题目：
Segment setTime Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2386 Accepted Submission(s): 924Problem DescriptionA 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. InputIn 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. OutputFor each Q-command, output the answer. There is a blank line between test cases. Sample Input110P 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 Output12225 AuthorLL SourceHDU 2006-12 Programming Contest Recommend
3、代码：
#include#include using namespace std;int set[1010];int num[1010];struct point{ double x,y;};struct edge{ point a; point b;}e[1010];int find(int x){ int r=x; while(r!=set[r]) r=set[r]; int i=x; while(i!=r) { int j=set[i]; set[i]=r; i=j; } return r;}void merge(int x,int y){ int fx=find(x); int fy=find(y); if(fx!=fy) { set[fx]=fy; num[fy]+=num[fx]; }}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,k,tmp,i,j; char s[10]; scanf("%d",&t); while(t--) { scanf("%d",&n); k=0; for(int i=1;i<=n;i++) { set[i]=i; num[i]=1; } for(int i=1;i<=n;i++) { scanf("%s",s); if(s[0]=='P') { k++; scanf("%lf%lf%lf%lf",&e[k].a.x,&e[k].a.y,&e[k].b.x,&e[k].b.y); for(int j=1;j
转载地址：http://eycdi.baihongyu.com/