计算几何扫描线题.
首先为了防止出现一些边界情况，(比如有一条无斜率的线段)，可以把点转一个角度。
用set维护当前的所有线段，并记录每条线段上方，最晚被插入/删除的后继的线段。
然后从左到右扫描线，
在每次加入线段的时候，考虑把加入的线段的左端点和set里的一个点连接起来。
考虑这个线段在set上的前驱，如果前驱上记录了点，那我就把这个点和记录的点连起来，否则我就和前驱这条线段的左端点连起来。 同时用当前这条线段的左端点来更新前驱记录的点。
在每次删除点的时候，更新一下set上的前驱记录的点即可。
复杂度(O(n log n).)
代码 :
#define db long double
const int N = 100050;
db Pi = acos(-1.0),theta = Pi * (1.0 * 139 / 180),cost = cos(theta),sint = sin(theta);
struct point{
db x,y; int realx,realy;
inline void calc(){ x = cost * realx - sint * realy,y = cost * realy + sint * realx; }
}p[N<<1]; int n;
inline void print(point a,point b){
cout << a.realx << ' ' << a.realy << ' ' << b.realx << ' ' << b.realy << '
';
}
struct Event{
int id,tp; db x;
bool operator < (Event w) const{ return x < w.x; }
}ev[N<<1];
db T;
struct line{
int s,t; mutable int lst; db k,b;
inline void calc(){ k = (p[s].y - p[t].y) / (p[s].x - p[t].x),b = p[s].y - k * p[s].x; }
bool operator < (const line w) const{ return k*T+b < w.k*T+w.b; }
}tmp;
set<line>S; set<line>::iterator it;
int main(){
int i;
ios::sync_with_stdio(0);
cin >> n;
for (i = 1; i <= n*2; i += 2){
cin >> p[i].realx >> p[i].realy,p[i].calc();
cin >> p[i+1].realx >> p[i+1].realy,p[i+1].calc();
if (p[i].x > p[i+1].x) swap(p[i],p[i+1]);
ev[i].id = i,ev[i].tp = 1,ev[i].x = p[i].x;
ev[i+1].id = i+1,ev[i+1].tp = 0,ev[i+1].x = p[i+1].x;
}
sort(ev+1,ev+(n<<1|1));
tmp.s = -2,tmp.t = tmp.lst = 0,tmp.k = 0,tmp.b = -1e10; S.insert(tmp);
tmp.s = -1,tmp.t = tmp.lst = 0,tmp.k = 0,tmp.b = 1e10; S.insert(tmp);
for (i = 1; i <= n*2; ++i){
T = ev[i].x;
if (ev[i].tp){
tmp.lst = tmp.s = ev[i].id,tmp.t = ev[i].id+1,tmp.calc();
it = S.insert(tmp).first,--it;
if (it->lst) print(p[it->lst],p[tmp.s]); it->lst = tmp.s;
}
else{
tmp.s = ev[i].id-1,tmp.t = ev[i].id,tmp.calc(),it = S.find(tmp),--it;
it->lst = tmp.t,S.erase(tmp);
}
}
return 0;
}