题意简述
多测。给定坐标系上依次给定\(n\)根木棍的起始和终止坐标，按顺序放置这些木棍，询问最终处在最上层的木棍有哪些。
\(n\le 100000\)。保证任意时刻最上层的木棍不超过\(1000\)个。
思路分析
看起来数据范围很刁钻，不过除了暴力以外的方法想不出了，就写了一份上交，结果过了。
思路就是用链表记录最上层的木棍，每放一根木棍就遍历链表，如果有相交的就把这个木棍从链表中移出去。
遍历完链表，再把当前木棍加进去。
难点主要在于如何判断木棍相交。
在平面上判断两线段相交，需要同时使用“快速排斥实验”与“跨立实验”。
所谓快速排斥实验，就是先粗略地判断一下两线段支起的矩形是否相交。如果两个矩形都不相交，两线段肯定也不相交。
但仅仅矩形相交显然不能说线段相交。还需要进行跨立实验。
从线段\(1\)的一端向线段\(2\)的两端作\(2\)个向量。记录红色向量和橙色向量的位置关系为\(A\)（顺时针/逆时针/共线）。
再从线段\(1\)的另一端向\(2\)的两端作\(2\)个向量。记位置关系为\(B\)。
再用线段\(2\)向线段\(1\)重复上面的过程，记位置关系为\(C,D\)。
如果\(A\)和\(B\)都是顺时针或者都是逆时针，或者\(C,D\)都是顺时针或者都是逆时针，则说明两线段不相交。
否则两线段相交。
注意到两向量可能出现共线的情况，这说明一定是某一点在一条线段上了。这种情况仍然是相交，所以不用参与判断。
Code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct point{double x,y;};
struct segment{point a,b;};
double cross(point a,point b){return a.x*b.y-b.x*a.y;}
point vec(point a,point b){return {b.x-a.x,b.y-a.y};}
bool intersect(segment a,segment b){
if(max(b.a.x,b.b.x)<min(a.a.x,a.b.x)||min(b.a.x,b.b.x)>max(a.a.x,a.b.x)||
max(b.a.y,b.b.y)<min(a.a.y,a.b.y)||min(b.a.y,b.b.y)>max(a.a.y,a.b.y)) return 0;
double t1=cross(vec(b.a,a.a),vec(b.a,a.b))*cross(vec(b.b,a.a),vec(b.b,a.b));
double t2=cross(vec(a.a,b.a),vec(a.a,b.b))*cross(vec(a.b,b.a),vec(a.b,b.b));
if(t1>0||t2>0) return 0;
return 1;
}
int n;
list<pair<int,segment>> li;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
while(cin>>n){
if(!n) break;
li.clear();
for(int i=1;i<=n;i++){
segment ts;
cin>>ts.a.x>>ts.a.y>>ts.b.x>>ts.b.y;
for(auto it=li.begin();it!=li.end();){
if(intersect(ts,(*it).second)) it=li.erase(it);
else it++;
}
li.push_back({i,ts});
}
cout<<"Top sticks: ";
bool f=0;
for(auto i:li){
if(!f) f=1;
else cout<<", ";
cout<<i.first;
if(!f) f=1,cout<<", ";
}
cout<<".\n";
}
return 0;
}