poj 2653 计算几何

 #include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
struct point {
double x,y;
};
point be[],en[];
int ans[];
int res[]; double max(double a,double b){
return a>b?a:b;
}
double min(double a,double b){
return a<b?a:b;
} int inter(point a,point b,point c,point d){
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))
return ;
double h,i,j,k;
h = (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
i = (d.x-a.x)*(b.y-a.y)-(d.y-a.y)*(b.x-a.x);
j = (a.x-c.x)*(d.y-c.y)-(a.y-c.y)*(d.x-c.x);
k = (b.x-c.x)*(d.y-c.y)-(b.y-c.y)*(d.x-c.x);
return h*i<&&j*k<;
}
int main()
{
int n;
while(scanf("%d",&n)==&&n){
for(int i=;i<n;i++)
cin>>be[i].x>>be[i].y>>en[i].x>>en[i].y;
memset(ans,,sizeof(ans));
memset(res,,sizeof(res));
for(int i=;i<n;i++){
for(int j=i+;j<n;j++){
if(inter(be[i],en[i],be[j],en[j])){
ans[i] =;
break;
}
}
}
int cnt =;
for(int i=;i<n;i++){
if(!ans[i])
res[cnt++] = i+;
}
printf("Top sticks: ");
for(int i=;i<cnt-;i++)
printf("%d, ",res[i]);
printf("%d.\n",res[cnt-]); }
return ;
}
上一篇:STM32 DMA使用详解


下一篇:利用ZYNQ SOC快速打开算法验证通路(4)——AXI DMA使用解析及环路测试