卫辉市住房和城市建设局网站,wordpress菜单小图标不显示,成都装修设计公司,阿里云网站建设视频xy方向分开考虑 用扫描线处理出拓扑序#xff0c;第二问直接回答拓扑序#xff0c; 第一问#xff1a; 将操作倒过来#xff0c;变成加入线段#xff0c;用线段树维护区间拓扑序的最值 #includecstdio
#includealgorithm
#includeset
#define N 1…xy方向分开考虑 用扫描线处理出拓扑序第二问直接回答拓扑序 第一问 将操作倒过来变成加入线段用线段树维护区间拓扑序的最值 #includecstdio
#includealgorithm
#includeset
#define N 100010
using namespace std;
inline void read(inta){char c;bool fa0;while(!((((cgetchar())0)(c9))||(c-)));if(c!-)ac-0;else f1;while(((cgetchar())0)(c9))(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 Linea,const Lineb){double xmax(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 AB;
}
setLineT;
struct Event{int x,id,type;Event(){}Event(int _x,int _id,int _type){x_x,id_id,type_type;}}b[N1];
inline bool operator (const Eventa,const Eventb){return a.xb.x||a.xb.xa.typeb.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[N2],v[N2],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 l1,rm,mid,t;while(lr)if(b[mid(lr)1].xx)r(tmid)-1;else lmid1;return t;
}
int l[N2],r[N2],vmin[N2],vmax[N2],tot,tagmin[N2],tagmax[N2];
void build(int a,int b){int xtot;vmin[x]tagmin[x]m,vmax[x]tagmax[x]0;if(a1b)return;int mid(ab)1;l[x]tot1;build(a,mid);r[x]tot1;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(cabd){vmax[x]max(vmax[x],p);vmin[x]min(vmin[x],p);return;}int mid(ab)1;if(cmid)ins(l[x],a,mid,c,d,p);if(dmid)ins(r[x],mid,b,c,d,p);
}
int askmin(int x,int a,int b,int c,int d){if(cabd)return min(vmin[x],tagmin[x]);int mid(ab)1,tvmin[x];if(cmid)tmin(t,askmin(l[x],a,mid,c,d));if(dmid)tmin(t,askmin(r[x],mid,b,c,d));return t;
}
int askmax(int x,int a,int b,int c,int d){if(cabd)return max(vmax[x],tagmax[x]);int mid(ab)1,tvmax[x];if(cmid)tmax(t,askmax(l[x],a,mid,c,d));if(dmid)tmax(t,askmax(r[x],mid,b,c,d));return t;
}
int judge(int d1,int d2){for(med0,i1;in;i)b[m]Event(a[i].s.x,i,1),b[m]Event(a[i].t.x,i,g[i]in[i]0);sort(b1,bm1);T.clear();for(i1;im;)for(jb[i].x;imb[i].xj;i){if(b[i].type)T.insert(a[b[i].id]);setLine::iterator pT.find(a[b[i].id]),kp;k;if(k!T.end())add(p-id,k-id);kp;if(k!T.begin())add((--k)-id,p-id);if(!b[i].type)T.erase(p);}for(hi1,t0;in;i)if(!in[i])q[t]i;while(ht)for(ig[q[h]];i;inxt[i])if(!(--in[v[i]]))q[t]v[i];for(i1;in;i)lx[i]lower(a[i].s.x),rx[i]lower(a[i].t.x),rank[q[i]]i;tot0;build(1,m);for(itn;i;i--){if(op[i][1]d1)if(rank[op[i][0]]askmax(1,1,m,lx[op[i][0]],rx[op[i][0]]))ti;if(op[i][1]d2)if(rank[op[i][0]]askmin(1,1,m,lx[op[i][0]],rx[op[i][0]]))ti;ins(1,1,m,lx[op[i][0]],rx[op[i][0]],rank[op[i][0]]);}return t;
}
int main(){for(read(n),i1;in;i){read(a[i].s.x),read(a[i].s.y),read(a[i].t.x),read(a[i].t.y),a[i].idi;if(a[i].s.xa[i].t.x)swap(a[i].s,a[i].t);}for(i1;in;i)read(op[i][0]),read(op[i][1]);for(ansjudge(i1,3);in;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.xa[i].t.x)swap(a[i].s,a[i].t);}for(printf(%d\n,min(ans,judge(2,0))),i1;in;i)printf(%d 3\n,my[i]);return 0;
}
