题意： 求有多少条线段没有与编号大于它的线段相交
解法： 数据随机，top stick不超过1000，可以直接暴力
知识点： 判断两个线段是否相交————向量叉积
代码：
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define N 200020
#define eps 1e-7
#define sosu double
using namespace std;
int n;
struct node{sosu x,y;};
struct line{node a,b;}p[N];
sosu cross(node o,node a,node b)
{sosu x1=a.x-o.x,x2=b.x-o.x;sosu y1=a.y-o.y,y2=b.y-o.y;return x1*y2-x2*y1;
}
bool check(line s,line t)
{sosu tmp=cross(s.a,s.b,t.a)*cross(s.a,s.b,t.b);sosu txp=cross(t.a,t.b,s.a)*cross(t.a,t.b,s.b);return tmp<-eps&&txp<-eps;
}
int ans[N],tot;
int main()
{while(~scanf("%d",&n)){tot=0;if(!n)break;for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&p[i].a.x,&p[i].a.y,&p[i].b.x,&p[i].b.y);for(int i=1;i<=n;i++){bool flag=0;for(int j=i+1;j<=n;j++)if(check(p[i],p[j])){flag=1;break;}if(!flag)ans[++tot]=i;}printf("Top sticks: ");for(int i=1;i<tot;i++)printf("%d, ",ans[i]);printf("%d.\n",ans[tot]);}
}