// 同樣是暴力，不同的暴力，一個TLE，一個5**MS
//判
線段相交
#include<iostream>
#include <math.h>
using namespace std;
#define MAXN 100000
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct point
{double x,y;};
struct line{ point a,b;};
line sti[MAXN+1];
bool under[MAXN+1];
//計算cross product (P1-P0)x(P2-P0)
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int dots_inline(point p1,point p2,point p3){
return zero(xmult(p1,p2,p3));
}
int same_side(point p1,point p2,line l){
return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;
}
int dot_online_in(point p,line l){
return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps;
}
int intersect_in(line u,line v){
if (!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b))
return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);
return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u);
}
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF && n)
{
memset(under,0,sizeof(under));
for(i=1;i<=n;i++)
scanf("%lf%lf%lf%lf",&(sti[i].a.x),&(sti[i].a.y),&(sti[i].b.x),&(sti[i].b.y));
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
if(intersect_in(sti[i],sti[j]))
{
under[i]=true;
break;
}
}
printf("Top sticks:");
for(i=1;i<n;i++)
if(!under[i])
printf(" %d,",i);
printf(" %d.\n",n);
}
return 0;
}posted on 2009-10-04 21:39
wyiu 閱讀(213)
評論(0) 編輯 收藏 引用 所屬分類:
POJ