POJ_2653_Pick-up sticks_線線相交
POJ_2653_Pick-up sticks_線線相交

POJ_2653_Pick-up sticks_線線相交
• 发表于 4年前
• 阅读 74
• 收藏 0
• 评论 0
``````#include <stdio.h>//POJ_2653_Pick-up sticks_線線相交
#include <stdlib.h>
#define EPS 1e-9

struct point{
double x,y;
};
struct Line{
point p1,p2;
}line[100002];

double MAX(double a,double b){
return a>b?a:b;
}

double MIN(double a,double b){
return a>b?b:a;
}

double mulit(point p0,point p1,point p2){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

int cross(Line a,Line b){//判断两线段是否相交
if(MAX(a.p1.x,a.p2.x)>MIN(b.p1.x,b.p2.x)&&
MAX(b.p1.x,b.p2.x)>MIN(a.p1.x,a.p2.x)&&
MAX(a.p1.y,a.p2.y)>MIN(b.p1.y,b.p2.y)&&
MAX(b.p1.y,b.p2.y)>MIN(a.p1.y,a.p2.y)&&
mulit(a.p1,a.p2,b.p1)*mulit(a.p1,a.p2,b.p2)<EPS&&
mulit(b.p1,b.p2,a.p1)*mulit(b.p1,b.p2,a.p2)<EPS)
return 1;
return 0;
}

int main(void)
{
int n,i,j;
while(1){
scanf("%d",&n);
if(n==0)break;
for(i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&line[i].p1.x,&line[i].p1.y,&line[i].p2.x,&line[i].p2.y);
}
printf("Top sticks:");
for(i=1;i<=n-1;i++){
for(j=i+1;j<=n;j++){
if(cross(line[i],line[j]))
break;
if(j==n) //若没有其他筷子与其相交，则该筷子是最上面筷子之一

printf(" %d,",i);
}
}
printf(" %d.\n",n);
}
return 0;
}

``````

×