首页 > 代码库 > ACM1558两线段相交判断和并查集
ACM1558两线段相交判断和并查集
Segment set
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 1P 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
题意是要求输入一些线段，判断这些线段连接成几个集合，然后求包含某条线段的集合中的元素个数；
本题主要难关是判断量条线段是否相交，在我这篇文章里有详细介绍判断两条线段相交的方法。http://www.cnblogs.com/sytu/articles/3876585.html;
Notice:二维向量的叉乘公式是 axb=(x1,y1)x(x2,y2)=x1*y2-y1*x2;
下面为AC代码：
1 #include<iostream> 2 using namespace std; 3 #define MIN(x,y) (x < y ? x : y) 4 #define MAX(x,y) (x > y ? x : y) 5 typedef struct 6 { 7 double x,y; 8 } Point; 9 struct LINE 10 { 11 double x1,x2,y1,y2; 12 int flag; 13 }; 14 LINE *line; 15 int lineintersect(int a,int b) 16 { 17 Point p1,p2,p3,p4; 18 p1.x=line[a].x1;p1.y=line[a].y1; 19 p2.x=line[a].x2;p2.y=line[a].y2; 20 p3.x=line[b].x1;p3.y=line[b].y1; 21 p4.x=line[b].x2;p4.y=line[b].y2; 22 23 Point tp1,tp2,tp3,tp4,tp5,tp6; 24 if ((p1.x==p3.x&&p1.y==p3.y)||(p1.x==p4.x&&p1.y==p4.y)||(p2.x==p3.x&&p2.y==p3.y)||(p2.x==p4.x&&p2.y==p4.y)) 25 return 1; 26 //快速排斥试验 27 if(MAX(p1.x,p2.x)<MIN(p3.x,p4.x)||MAX(p3.x,p4.x)<MIN(p1.x,p2.x)||MAX(p1.y,p2.y)<MIN(p3.y,p4.y)||MAX(p3.y,p4.y)<MIN(p1.y,p2.y)) 28 return 0; 29 //跨立试验 30 tp1.x=p1.x-p3.x; 31 tp1.y=p1.y-p3.y; 32 tp2.x=p4.x-p3.x; 33 tp2.y=p4.y-p3.y; 34 tp3.x=p2.x-p3.x; 35 tp3.y=p2.y-p3.y;//从这到上面是一组的向量 36 tp4.x=p2.x-p4.x;//下面是一组的向量 37 tp4.y=p2.y-p4.y; 38 tp5.x=p2.x-p3.x; 39 tp5.y=p2.y-p3.y; 40 tp6.x=p2.x-p1.x; 41 tp6.y=p2.y-p1.y; 42 if ((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0) //此处用到了叉乘公式 43 { 44 if((tp4.x*tp6.y-tp4.y*tp6.x)*(tp6.x*tp5.y-tp6.y*tp5.x)>=0) 45 return 1; 46 } 47 return 0; 48 } 49 int find(int x) 50 { 51 if(0>line[x].flag)return x; 52 return line[x].flag=find(line[x].flag); 53 } 54 void Union(int a,int b) 55 { 56 int fa=find(a); 57 int fb=find(b); 58 if(fa==fb)return; 59 int n1=line[fa].flag; 60 int n2=line[fb].flag; 61 if(n1>n2) 62 { 63 line[fa].flag=fb; 64 line[fb].flag+=n1; 65 } 66 else 67 { 68 line[fb].flag=fa; 69 line[fa].flag+=n2; 70 } 71 } 72 void throwinto(int n) 73 { 74 if(n>1) 75 { 76 for(int i=1;i<n;i++) 77 { 78 if(lineintersect(i,n)) 79 Union(i,n); 80 } 81 } 82 } 83 int main() 84 { 85 int t; 86 cin>>t; 87 int n,q; 88 int cn=t; 89 while(t--) 90 { 91 92 int cnt=1; 93 cin>>n; 94 line=new LINE[n+1]; 95 for(int i=0;i<=n;i++) 96 { 97 line[i].flag=-1; 98 } 99 for(int i=1;i<=n;i++)100 {101 char sj;102 cin>>sj;103 if(sj==‘P‘)104 {105 cin>>line[cnt].x1>>line[cnt].y1>>line[cnt].x2>>line[cnt].y2;106 throwinto(cnt);107 cnt++;108 }109 else if(sj==‘Q‘)110 {111 cin>>q;112 int re=find(q);113 cout<<-line[re].flag<<endl;114 }115 }116 if(t>0)cout<<endl;//注意格式问题，容易出错117 }118 return 0;119 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。