首页 > 代码库 > HDU HDU1558 Segment set（并查集+判断线段相交）
HDU HDU1558 Segment set（并查集+判断线段相交）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1558
解题报告：首先如果两条线段有交点的话，这两条线段在一个集合内，如果a跟b在一个集合内，b跟c在一个集合内，那么a跟c在一个集合内。在一个平面上，有两种操作：
P：在这个平面上添加一条线段
Q k：询问添加的第k条线段所在的那个集合有多少条线段
用并查集，然后就是要判断一下线段有没有交点。还有就是题目要求两个test之间要有空行，为此我还PE了一次。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int maxn = 1005; 8 const double eps = 1e-6; 9 struct point 10 { 11 double x,y; 12 point(double x = 0,double y = 0):x(x),y(y) {} 13 inline friend point operator + (point p1,point p2) 14 { 15 return point(p1.x+p2.x,p1.y+p2.y); 16 } 17 inline friend point operator - (point p1,point p2) 18 { 19 return point(p1.x-p2.x,p1.y-p2.y); 20 } 21 }pos[maxn]; 22 struct line 23 { 24 point s,e; 25 int flag; 26 }L[maxn]; 27 int pre[maxn]; 28 int find(int d) 29 { 30 return pre[d] == d? d:pre[d] = find(pre[d]); 31 } 32 inline double dot(point p1,point p2) //求叉积 33 { 34 return p1.x*p2.y - p2.x*p1.y; 35 } 36 int judge(point p1,point p2,point p3,point p4) //判断线段没有没交点 37 { 38 double temp1 = dot(p1-p3,p4-p3) * dot(p2-p3,p4-p3); 39 double temp2 = dot(p3-p1,p2-p1) * dot(p4-p1,p2-p1); 40 if((temp1 < 0 || fabs(temp1) < eps) && (temp2 < 0 || fabs(temp2) < eps)) return 1; 41 return 0; 42 } 43 int T,n,m; 44 void push(line t,line* L,int m) 45 { 46 for(int i = 1;i < m;++i) 47 if(judge(L[i].s,L[i].e,t.s,t.e)) 48 { 49 pre[find(t.flag)] = find(L[i].flag); 50 // break; 51 } 52 L[m] = t; 53 } 54 int query(int k) 55 { 56 int temp = find(k),ans = 0; 57 for(int i = 1;i <= m;++i) 58 if(find(i) == temp) 59 ans++; 60 return ans; 61 } 62 int main() 63 { 64 // freopen("in","r",stdin); 65 double x1,y1,x2,y2; 66 scanf("%d",&T); 67 for(int l = 0;l < T;++l) 68 { 69 if(l) puts(""); 70 scanf("%d",&n); 71 for(int i = 0;i <= 1000;++i) //初始化并查集 72 pre[i] = i; 73 char oper[5]; 74 m = 0; //初始化当前线段的数量 75 while(n--) 76 { 77 scanf("%s",oper); 78 if(oper[0] == ‘P‘) 79 { 80 line temp; 81 scanf("%lf%lf%lf%lf",&temp.s.x,&temp.s.y,&temp.e.x,&temp.e.y); 82 temp.flag = ++m; 83 push(temp,L,m); 84 } 85 else if(oper[0] == ‘Q‘) 86 { 87 int k; 88 scanf("%d",&k); 89 printf("%d\n",query(k)); 90 } 91 } 92 // for(int i = 1;i <= m;++i) 93 // { 94 // for(int j = 1;j <= m;++j) 95 // printf(judge(L[i].s,L[i].e,L[j].s,L[j].e)? "1 ":"0 "); 96 // printf("\n"); 97 // } 98 } 99 return 0;100 }
HDU HDU1558 Segment set（并查集+判断线段相交）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。