题意：给定n个木棍依次放下，要求最终判断没被覆盖的木棍是哪些。
思路:快速排斥以及跨立实验可以判断线段相交。
1 #include<algorithm> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 const double eps=1e-10; 7 struct Point{ 8 double x,y; 9 Point(){} 10 Point(double x0,double y0):x(x0),y(y0){} 11 }s[200005],e[200005]; 12 int ans[200005],st[200005],n; 13 double operator *(Point p1,Point p2){ 14 return p1.x*p2.y-p1.y*p2.x; 15 } 16 Point operator -(Point p1,Point p2){ 17 return Point(p1.x-p2.x,p1.y-p2.y); 18 } 19 bool judge(Point p1,Point p2,Point p3,Point p4){ 20 if (std::min(p1.x,p2.x)>std::max(p3.x,p4.x)|| 21 std::min(p1.y,p2.y)>std::max(p3.y,p4.y)|| 22 std::min(p3.x,p4.x)>std::max(p1.x,p2.x)|| 23 std::min(p3.y,p4.y)>std::max(p1.y,p2.y)) 24 return 0;//快速排斥实验 25 double a,b,c,d; 26 a=(p2-p1)*(p3-p1); 27 b=(p2-p1)*(p4-p1); 28 c=(p4-p3)*(p1-p3); 29 d=(p4-p3)*(p2-p3); 30 return (a*b<=eps)&&(c*d<=eps);//跨立实验 31 } 32 int main(){ 33 while (scanf("%d",&n)!=EOF&&n){ 34 for (int i=1;i<=n;i++) ans[i]=0; 35 for (int i=1;i<=n;i++){ 36 scanf("%lf%lf%lf%lf",&s[i].x,&s[i].y,&e[i].x,&e[i].y); 37 } 38 for (int i=1;i<=n;i++) 39 for (int j=i+1;j<=n;j++) 40 if (judge(s[i],e[i],s[j],e[j])) 41 { ans[i]=1; 42 break; 43 } 44 int top=0; 45 for (int i=1;i<=n;i++) 46 if (!ans[i]) 47 st[++top]=i; 48 printf("Top sticks:"); 49 for (int i=1;i<top;i++) 50 printf(" %d,",st[i]); 51 printf(" %d. ",st[top]); 52 } 53 }