题意：给定n个木棍依次放下，要求最终判断没被覆盖的木棍是哪些。
思路:快速排斥以及跨立实验可以判断线段相交。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
const double eps=1e-;
struct Point{
double x,y;
Point(){}
Point(double x0,double y0):x(x0),y(y0){}
}s[],e[];
int ans[],st[],n;
double operator *(Point p1,Point p2){
return p1.x*p2.y-p1.y*p2.x;
}
Point operator -(Point p1,Point p2){
return Point(p1.x-p2.x,p1.y-p2.y);
}
bool judge(Point p1,Point p2,Point p3,Point p4){
if (std::min(p1.x,p2.x)>std::max(p3.x,p4.x)||
std::min(p1.y,p2.y)>std::max(p3.y,p4.y)||
std::min(p3.x,p4.x)>std::max(p1.x,p2.x)||
std::min(p3.y,p4.y)>std::max(p1.y,p2.y))
return ;//快速排斥实验
double a,b,c,d;
a=(p2-p1)*(p3-p1);
b=(p2-p1)*(p4-p1);
c=(p4-p3)*(p1-p3);
d=(p4-p3)*(p2-p3);
return (a*b<=eps)&&(c*d<=eps);//跨立实验
}
int main(){
while (scanf("%d",&n)!=EOF&&n){
for (int i=;i<=n;i++) ans[i]=;
for (int i=;i<=n;i++){
scanf("%lf%lf%lf%lf",&s[i].x,&s[i].y,&e[i].x,&e[i].y);
}
for (int i=;i<=n;i++)
for (int j=i+;j<=n;j++)
if (judge(s[i],e[i],s[j],e[j]))
{ ans[i]=;
break;
}
int top=;
for (int i=;i<=n;i++)
if (!ans[i])
st[++top]=i;
printf("Top sticks:");
for (int i=;i<top;i++)
printf(" %d,",st[i]);
printf(" %d.\n",st[top]);
}
}