首页 > 代码库 > POJ 2653 Pick-up sticks(线段相交)
POJ 2653 Pick-up sticks(线段相交)
题目链接
题意 : 把每根棍往地上扔,找出最后在上面的棍,也就是说找出所有的没有别的棍子压在它的上面的棍子。
思路 : 对于每根棍子,压在他上面的棍子一定是在它之后扔的棍子,所以在找的时候只要找它之后的线段是否与他相交即可。
1 //2653 2 #include <stdio.h> 3 #include <iostream> 4 #include <math.h> 5 #include <string.h> 6 7 using namespace std ; 8 9 struct point10 {11 double x,y ;12 }p[200100];13 struct line14 {15 point a,b ;16 }L[101000];17 int ans[1100] ;18 19 double multi(point a,point b,point c)20 {21 return ((a.x-c.x) * (b.y-c.y) - (b.x-c.x)*(a.y-c.y)) ;22 }23 bool intersect(point a,point b,point c,point d)//非规范相交24 {25 if(max(a.x,b.x) < min(c.x,d.x) || max(a.y,b.y) < min(c.y,d.y) || max(c.x,d.x) < min(a.x,b.x) || max(c.y,d.y) < min(a.y,b.y))26 return false ;27 if(multi(c,b,a) * multi(b,d,a) < 0 || multi(a,d,c)*multi(d,b,c) < 0) return false ;28 return true ;29 }30 int main()31 {32 int n ;33 while(~scanf("%d",&n))34 {35 if(n == 0) break ;36 for(int i = 1 ; i <= n ; i++)37 scanf("%lf %lf %lf %lf",&L[i].a.x,&L[i].a.y,&L[i].b.x,&L[i].b.y) ;38 int cnt = 0 ;39 for(int i = 1 ; i < n ; i++)40 {41 bool flag = true ;42 for(int j = i+1 ;j <= n ; j++)43 {44 if(intersect(L[i].a,L[i].b,L[j].a,L[j].b))45 {46 flag = false ;47 break ;48 }49 }50 if(flag) ans[cnt ++] = i ;51 }52 printf("Top sticks: ") ;53 for(int i = 0 ; i < cnt ; i++)54 {55 printf("%d, ",ans[i]) ;56 }57 printf("%d.\n",n) ;58 }59 return 0 ;60 }
POJ 2653 Pick-up sticks(线段相交)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。