xy方向分开考虑
用扫描线处理出拓扑序，第二问直接回答拓扑序，
第一问：
将操作倒过来，变成加入线段，用线段树维护区间拓扑序的最值
#include<cstdio>
#include<algorithm>
#include<set>
#define N 100010
using namespace std;
inline void read(int&a){char c;bool f=a=0;while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));if(c!='-')a=c-'0';else f=1;while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';if(f)a=-a;}
struct Point{int x,y;Point(){}Point(int _x,int _y){x=_x,y=_y;}};
struct Line{Point s,t;int id;}a[N];
inline bool operator <(const Line&a,const Line&b){
double x=max(a.s.x,b.s.x),A=(x-a.s.x)/(a.t.x-a.s.x)*(a.t.y-a.s.y)+a.s.y,B=(x-b.s.x)/(b.t.x-b.s.x)*(b.t.y-b.s.y)+b.s.y;
return A<B;
}
set<Line>T;
struct Event{int x,id,type;Event(){}Event(int _x,int _id,int _type){x=_x,id=_id,type=_type;}}b[N<<1];
inline bool operator <(const Event&a,const Event&b){return a.x<b.x||a.x==b.x&&a.type<b.type;}
int n,i,j,m,h,t,q[N],my[N],op[N][2],lx[N],rx[N],rank[N],ans,g[N],nxt[N<<2],v[N<<2],in[N],ed;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;in[y]++;}
inline int lower(int x){
int l=1,r=m,mid,t;
while(l<=r)if(b[mid=(l+r)>>1].x>=x)r=(t=mid)-1;else l=mid+1;
return t;
}
int l[N<<2],r[N<<2],vmin[N<<2],vmax[N<<2],tot,tagmin[N<<2],tagmax[N<<2];
void build(int a,int b){
int x=++tot;
vmin[x]=tagmin[x]=m,vmax[x]=tagmax[x]=0;
if(a+1==b)return;
int mid=(a+b)>>1;
l[x]=tot+1;build(a,mid);
r[x]=tot+1;build(mid,b);
}
void ins(int x,int a,int b,int c,int d,int p){
tagmax[x]=max(tagmax[x],p);tagmin[x]=min(tagmin[x],p);
if(c<=a&&b<=d){vmax[x]=max(vmax[x],p);vmin[x]=min(vmin[x],p);return;}
int mid=(a+b)>>1;
if(c<mid)ins(l[x],a,mid,c,d,p);
if(d>mid)ins(r[x],mid,b,c,d,p);
}
int askmin(int x,int a,int b,int c,int d){
if(c<=a&&b<=d)return min(vmin[x],tagmin[x]);
int mid=(a+b)>>1,t=vmin[x];
if(c<mid)t=min(t,askmin(l[x],a,mid,c,d));
if(d>mid)t=min(t,askmin(r[x],mid,b,c,d));
return t;
}
int askmax(int x,int a,int b,int c,int d){
if(c<=a&&b<=d)return max(vmax[x],tagmax[x]);
int mid=(a+b)>>1,t=vmax[x];
if(c<mid)t=max(t,askmax(l[x],a,mid,c,d));
if(d>mid)t=max(t,askmax(r[x],mid,b,c,d));
return t;
}
int judge(int d1,int d2){
for(m=ed=0,i=1;i<=n;i++)b[++m]=Event(a[i].s.x,i,1),b[++m]=Event(a[i].t.x,i,g[i]=in[i]=0);
sort(b+1,b+m+1);
T.clear();
for(i=1;i<=m;)for(j=b[i].x;i<=m&&b[i].x==j;i++){
if(b[i].type)T.insert(a[b[i].id]);
set<Line>::iterator p=T.find(a[b[i].id]),k=p;
++k;
if(k!=T.end())add(p->id,k->id);
k=p;
if(k!=T.begin())add((--k)->id,p->id);
if(!b[i].type)T.erase(p);
}
for(h=i=1,t=0;i<=n;i++)if(!in[i])q[++t]=i;
while(h<=t)for(i=g[q[h++]];i;i=nxt[i])if(!(--in[v[i]]))q[++t]=v[i];
for(i=1;i<=n;i++)lx[i]=lower(a[i].s.x),rx[i]=lower(a[i].t.x),rank[q[i]]=i;
tot=0;build(1,m);
for(i=t=n;i;i--){
if(op[i][1]==d1)if(rank[op[i][0]]<askmax(1,1,m,lx[op[i][0]],rx[op[i][0]]))t=i;
if(op[i][1]==d2)if(rank[op[i][0]]>askmin(1,1,m,lx[op[i][0]],rx[op[i][0]]))t=i;
ins(1,1,m,lx[op[i][0]],rx[op[i][0]],rank[op[i][0]]);
}
return t;
}
int main(){
for(read(n),i=1;i<=n;i++){
read(a[i].s.x),read(a[i].s.y),read(a[i].t.x),read(a[i].t.y),a[i].id=i;
if(a[i].s.x>a[i].t.x)swap(a[i].s,a[i].t);
}
for(i=1;i<=n;i++)read(op[i][0]),read(op[i][1]);
for(ans=judge(i=1,3);i<=n;i++){
my[i]=q[i],swap(a[i].s.x,a[i].s.y),swap(a[i].t.x,a[i].t.y);
if(a[i].s.x>a[i].t.x)swap(a[i].s,a[i].t);
}
for(printf("%d
",min(ans,judge(2,0))),i=1;i<=n;i++)printf("%d 3
",my[i]);
return 0;
}