题解：
从左往右加入每一个点
判断一下和,pre,nxt是否相交
删除得时候也要判断
代码：
#pragma GCC optimize(2) #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=200010; typedef double ld; const ld eps=1e-8,C=0.18479956785822313167427314019291; struct nd{int id,ls,rs,rk,fa;ld key;}t[N]; struct se{ld x1,y1,x2,y2,k,b;}s[N]; struct Tp{ld sg,x;int id;}p[N]; int n,m,rt,date[N]; int cmp(const Tp &a,const Tp &b){return (a.x<b.x);} void rotate(ld &x,ld &y) { ld p=x,q=y; x=cos(C)*p-sin(C)*q; y=sin(C)*p+cos(C)*q; } int zig(int d) { int tmp=t[d].ls; t[d].ls=t[tmp].rs;t[tmp].rs=d; t[tmp].fa=t[d].fa; t[d].fa=tmp; if (t[d].ls) t[t[d].ls].fa=d; return tmp; } int zag(int d) { int tmp=t[d].rs; t[d].rs=t[tmp].ls;t[tmp].ls=d; t[tmp].fa=t[d].fa; t[d].fa=tmp; if (t[d].rs) t[t[d].rs].fa=d; return tmp; } int ins(int d,ld y,ld x,int id) { if (!d) { date[id]=++m; t[m].key=y;t[m].id=id; t[m].fa=0;t[m].rk=rand(); return m; } ld _y=s[t[d].id].k*x+s[t[d].id].b; if (fabs(y-_y)<=eps) { printf("YES %d %d ",id+1,t[d].id+1); exit(0); } if (y<_y) { t[d].ls=ins(t[d].ls,y,x,id); t[t[d].ls].fa=d; if (t[t[d].ls].rk<t[d].rk)return zig(d); else return d; } t[d].rs=ins(t[d].rs,y,x,id); t[t[d].rs].fa=d; if (t[t[d].rs].rk<t[d].rk)return zag(d); else return d; } int del(int d,ld y,ld x) { ld _y=s[t[d].id].k*x+s[t[d].id].b; if (fabs(y-_y)<=eps) { if (!(t[d].ls+t[d].rs)) return 0; if ((t[d].ls)&&((!t[d].rs)||(t[t[d].ls].rk<t[t[d].rs].rk)))d=zig(d); else d=zag(d); return del(d,y,x); } if (y<_y)t[d].ls=del(t[d].ls,y,x); else t[d].rs=del(t[d].rs,y,x); return d; } int pre(int d) { if (t[d].ls) { for (d=t[d].ls;t[d].rs;d=t[d].rs); return d; } while (d) { if (t[t[d].fa].rs==d) return t[d].fa; d=t[d].fa; } return -1; } int nxt(int d) { if (t[d].rs) { for (d=t[d].rs;t[d].ls;d=t[d].ls); return d; } while (d) { if (t[t[d].fa].ls==d) return t[d].fa; d=t[d].fa; } return -1; } int det(ld x1,ld y1,ld x2,ld y2,ld x3,ld y3) { ld res=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1); if (fabs(res)<=eps) return 0; if (res>0) return 1; else return -1; } int cr(int a,int b) { if ((a==-1)||(b==-1)) return 0; a=t[a].id;b=t[b].id; if ((s[a].x1+eps>=min(s[b].x1,s[b].x2))&&(s[a].x1-eps<=max(s[b].x1,s[b].x2)) &&(!det(s[b].x1,s[b].y1,s[b].x2,s[b].y2,s[a].x1,s[a].y1)))return 1; if ((s[a].x2+eps>=min(s[b].x1,s[b].x2))&&(s[a].x2-eps<=max(s[b].x1,s[b].x2)) &&(!det(s[b].x1,s[b].y1,s[b].x2,s[b].y2,s[a].x2,s[a].y2)))return 1; if ((s[b].x1+eps>=min(s[a].x1,s[a].x2))&&(s[b].x1-eps<=max(s[a].x1,s[a].x2)) &&(!det(s[a].x1,s[a].y1,s[a].x2,s[a].y2,s[b].x1,s[b].y1)))return 1; if ((s[b].x2+eps>=min(s[a].x1,s[a].x2))&&(s[b].x2-eps<=max(s[a].x1,s[a].x2)) &&(!det(s[a].x1,s[a].y1,s[a].x2,s[a].y2,s[b].x2,s[b].y2)))return 1; if ((det(s[a].x1,s[a].y1,s[a].x2,s[a].y2,s[b].x1,s[b].y1)* det(s[a].x1,s[a].y1,s[a].x2,s[a].y2,s[b].x2,s[b].y2)<0)&& (det(s[b].x1,s[b].y1,s[b].x2,s[b].y2,s[a].x1,s[a].y1)* det(s[b].x1,s[b].y1,s[b].x2,s[b].y2,s[a].x2,s[a].y2)<0))return 1; else return 0; } int main() { scanf("%d",&n); for (int i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&s[i].x1,&s[i].y1,&s[i].x2,&s[i].y2); rotate(s[i].x1,s[i].y1);rotate(s[i].x2,s[i].y2); if (s[i].x1>s[i].x2) swap(s[i].x1,s[i].x2),swap(s[i].y1,s[i].y2); s[i].k=(s[i].y2-s[i].y1)/(s[i].x2-s[i].x1); s[i].b=s[i].y1-s[i].k*s[i].x1; p[i].id=p[i+n].id=i; p[i].sg=1;p[i+n].sg=0; p[i].x=s[i].x1;p[i+n].x=s[i].x2; } sort(p,p+n*2,cmp); for (int i=0;i<n*2;i++) if (p[i].sg) { rt=ins(rt,s[p[i].id].y1,p[i].x,p[i].id); if (cr(date[p[i].id],pre(m))) { printf("YES %d %d",p[i].id+1,t[pre(m)].id+1); return 0; } if (cr(date[p[i].id],nxt(m))) { printf("YES %d %d",p[i].id+1,t[nxt(m)].id+1); return 0; } } else { if (cr(pre(date[p[i].id]),nxt(date[p[i].id]))) { printf("YES %d %d",t[pre(date[p[i].id])].id+1, t[nxt(date[p[i].id])].id+1); return 0; } rt=del(rt,s[p[i].id].y2,p[i].x); } puts("NO"); return 0; }