首页 > 代码库 > HDU 1558 Segment set （并查集+线段非规范相交）
HDU 1558 Segment set （并查集+线段非规范相交）
题目链接
题意 ： 如果两个线段相交就属于同一集合，查询某条线段所属集合有多少线段，输出。
思路 ： 先判断与其他线段是否相交，然后合并。
1 //1558 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <cmath> 6 #define eps 1e-8 7 #define zero(x) (((x) > 0 ? (x) : (-x)) < eps) 8 9 using namespace std ; 10 11 struct point 12 { 13 double x,y ; 14 } p[1010]; 15 struct Line 16 { 17 point a; 18 point b ; 19 // int num ; 20 } L[1010] ; 21 int father[1010],numb[1010],rankk[1010] ; 22 int cnt ; 23 double direction(point p0,point p1,point p2) 24 { 25 return (p2.x-p0.x)*(p1.y-p0.y)-(p1.x-p0.x)*(p2.y-p0.y); 26 } 27 28 bool on_segment(point p0,point p1,point p2) 29 { 30 if((min(p0.x,p1.x)<=p2.x && p2.x<=max(p0.x,p1.x)) && (min(p0.y,p1.y)<=p2.y && p2.y<=max(p0.y,p1.y))) 31 return true; 32 return false; 33 } 34 35 bool Segment_intersect(point p1,point p2,point p3,point p4) 36 { 37 double d1,d2,d3,d4; 38 d1 = direction(p3,p4,p1); 39 d2 = direction(p3,p4,p2); 40 d3 = direction(p1,p2,p3); 41 d4 = direction(p1,p2,p4); 42 if(((d1>0 && d2<0)||(d1<0 && d2>0)) && ((d3>0 && d4<0)||(d3<0&&d4>0))) 43 return true; 44 else if((d1==0 && on_segment(p3,p4,p1)) || (d2==0 && on_segment(p3,p4,p2)) || (d3==0 && on_segment(p1,p2,p3)) || (d4==0 && on_segment(p1,p2,p4))) 45 return true; 46 return false; 47 } 48 int find_(int x) 49 { 50 if(father[x] != x) 51 father[x] = find_(father[x]) ; 52 return father[x] ; 53 } 54 55 void mergee(int a, int b){ 56 int fx = find_(a); 57 int fy = find_(b); 58 59 if (fx != fy){ 60 father[fy] = fx; 61 numb[fx] += numb[fy]; 62 } 63 } 64 void Init() 65 { 66 cnt = 0 ; 67 for(int i=0; i<=1010; i++) 68 { 69 numb[i]=1; 70 } 71 for(int i = 0 ; i < 1010 ; i++) 72 father[i] = i ; 73 memset(rankk,0,sizeof(rankk)) ; 74 } 75 int main() 76 { 77 int T ,n,ss; 78 scanf("%d",&T) ; 79 char s[4] ; 80 while( T--) 81 { 82 scanf("%d",&n) ; 83 Init() ; 84 for(int i = 0 ; i < n ; i++) 85 { 86 scanf("%s",s) ; 87 if(s[0] == ‘P‘) 88 { 89 cnt ++ ; 90 scanf("%lf %lf %lf %lf",&L[cnt].a.x,&L[cnt].a.y,&L[cnt].b.x,&L[cnt].b.y) ; 91 for(int j = 1 ; j < cnt ; j ++) 92 if(find_(j) != find_(cnt) && Segment_intersect(L[j].a,L[j].b,L[cnt].a,L[cnt].b)) 93 mergee(j,cnt) ; 94 } 95 else 96 { 97 scanf("%d",&ss) ; 98 printf("%d\n",numb[find_(ss)]) ; 99 }100 }101 if(T) printf("\n") ;102 }103 return 0 ;104 }
线段非规范相交1
1 double cross(point p0,point p1,point p2) 2 { 3 return (p2.x-p0.x)*(p1.y-p0.y)-(p1.x-p0.x)*(p2.y-p0.y); 4 } 5 6 bool on_segment(point p0,point p1,point p2) 7 { 8 if((min(p0.x,p1.x)<=p2.x && p2.x<=max(p0.x,p1.x)) && (min(p0.y,p1.y)<=p2.y && p2.y<=max(p0.y,p1.y))) 9 return true;10 return false;11 }12 13 bool Segment_intersect(point p1,point p2,point p3,point p4)14 {15 double d1,d2,d3,d4;16 d1 = cross(p3,p4,p1);17 d2 = cross(p3,p4,p2);18 d3 = cross(p1,p2,p3);19 d4 = cross(p1,p2,p4);20 if(((d1>0 && d2<0)||(d1<0 && d2>0)) && ((d3>0 && d4<0)||(d3<0&&d4>0)))21 return true;22 else if((d1==0 && on_segment(p3,p4,p1)) || (d2==0 && on_segment(p3,p4,p2)) || (d3==0 && on_segment(p1,p2,p3)) || (d4==0 && on_segment(p1,p2,p4)))23 return true;24 return false;25 }
线段非规范相交2
1 double cross(point a, point b, point c) 2 { 3 return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); 4 } 5 6 //aa, bb为一条线段两端点 cc, dd为另一条线段的两端点 相交返回true, 不相交返回false 7 bool intersect(point aa, point bb, point cc, point dd) 8 { 9 if ( max(aa.x, bb.x)<min(cc.x, dd.x) )10 {11 return false;12 }13 if ( max(aa.y, bb.y)<min(cc.y, dd.y) )14 {15 return false;16 }17 if ( max(cc.x, dd.x)<min(aa.x, bb.x) )18 {19 return false;20 }21 if ( max(cc.y, dd.y)<min(aa.y, bb.y) )22 {23 return false;24 }25 if ( cross(cc, bb, aa)*cross(bb, dd, aa)<0 )26 {27 return false;28 }29 if ( cross(aa, dd, cc)*cross(dd, bb, cc)<0 )30 {31 return false;32 }33 return true;34 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。