首页 > 代码库 > poj 2653 计算几何
poj 2653 计算几何
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstdio> 6 using namespace std; 7 struct point { 8 double x,y; 9 }; 10 point be[100005],en[100005]; 11 int ans[100005]; 12 int res[100005]; 13 14 double max(double a,double b){ 15 return a>b?a:b; 16 } 17 double min(double a,double b){ 18 return a<b?a:b; 19 } 20 21 int inter(point a,point b,point c,point d){ 22 if(min(a.x,b.x)>max(c.x,d.x)||min(a.y,b.y)>max(c.y,d.y)||min(c.x,d.x)>max(a.x,b.x)||min(c.y,d.y)>max(a.y,b.y)) 23 return 0; 24 double h,i,j,k; 25 h = (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x); 26 i = (d.x-a.x)*(b.y-a.y)-(d.y-a.y)*(b.x-a.x); 27 j = (a.x-c.x)*(d.y-c.y)-(a.y-c.y)*(d.x-c.x); 28 k = (b.x-c.x)*(d.y-c.y)-(b.y-c.y)*(d.x-c.x); 29 return h*i<0&&j*k<0; 30 } 31 int main() 32 { 33 int n; 34 while(scanf("%d",&n)==1&&n){ 35 for(int i=0;i<n;i++) 36 cin>>be[i].x>>be[i].y>>en[i].x>>en[i].y; 37 memset(ans,0,sizeof(ans)); 38 memset(res,0,sizeof(res)); 39 for(int i=0;i<n;i++){ 40 for(int j=i+1;j<n;j++){ 41 if(inter(be[i],en[i],be[j],en[j])){ 42 ans[i] =1; 43 break; 44 } 45 } 46 } 47 int cnt =0; 48 for(int i=0;i<n;i++){ 49 if(!ans[i]) 50 res[cnt++] = i+1; 51 } 52 printf("Top sticks: "); 53 for(int i=0;i<cnt-1;i++) 54 printf("%d, ",res[i]); 55 printf("%d.\n",res[cnt-1]); 56 57 } 58 return 0; 59 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。