#include #define debug(x) cerr<<#x<<" = "< #define mp make_pair #define pb push_back using namespace std; namespace IO{ const int BS=(1<<23)+5; int Top=0; char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1; char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;} void flush(){fwrite(OT,1,OS-OT,stdout),OS=OT;} void Putchar(char c){*OS++ =c;if(OS==fin)flush();} void write(int x){ if(!x){Putchar('0');return;} if(x<0) x=-x,Putchar('-'); while(x) SS[++Top]=x%10,x/=10; while(Top) Putchar(SS[Top]+'0'),--Top; } inline LL read(){ LL nm=0; bool fh=1; char cw=getchar(); for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-'); for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0'); return fh?nm:-nm; } } using namespace IO; #define M 420 const DB INF=1e14; //const int dy[]={1,0,-1,0}; //const int dy[]={0,1,0,-1}; int n,mx,my,nx[M],ny[M],lx[M],rx[M],ly[M],ry[M],sx,sy,ex,ey,xx[M][M],yy[M][M]; struct sta{ int x,y; LDB now; sta(){} sta(int _x,int _y,LDB _now){x=_x,y=_y,now=_now;} inline bool operator <(const sta&ot)const{return now>ot.now;} }; priority_queueQ; LDB dis[M][M]; bool vs[M][M]; inline void upd(int x,int y,LDB now,int cov,int len){ LDB tar=now+(LDB)len/(LDB)(cov+1); if(dis[x][y]>tar) Q.push(sta(x,y,dis[x][y]=tar)); } inline LDB solve(){ n=read(),mx=0,my=0; for(int i=1;i<=n;i++){ lx[i]=read(),ly[i]=read(),rx[i]=read(),ry[i]=read(); nx[++mx]=lx[i],nx[++mx]=rx[i]; ny[++my]=ly[i],ny[++my]=ry[i]; } memset(vs,false,sizeof(vs)); sx=read(),sy=read(),ex=read(),ey=read(); nx[++mx]=sx,nx[++mx]=ex; ny[++my]=sy,ny[++my]=ey; sort(nx+1,nx+mx+1),sort(ny+1,ny+my+1); mx=unique(nx+1,nx+mx+1)-nx-1; my=unique(ny+1,ny+my+1)-ny-1; // debug(mx)sp,debug(my)el; // for(int i=1;i<=4;i++) debug(i)sp,debug(nx[i])sp,debug(ny[i])el; memset(xx,0,sizeof(xx)),memset(yy,0,sizeof(yy)); for(int i=1;i<=n;i++){ int l1=lower_bound(nx+1,nx+mx+1,lx[i])-nx; int r1=lower_bound(nx+1,nx+mx+1,rx[i])-nx; int l2=lower_bound(ny+1,ny+my+1,ly[i])-ny; int r2=lower_bound(ny+1,ny+my+1,ry[i])-ny; for(int i=l1;i<=r1;i++) xx[i][l2]++,xx[i][r2]--; for(int i=l2;i<=r2;i++) yy[i][l1]++,yy[i][r1]--; } sx=lower_bound(nx+1,nx+mx+1,sx)-nx; sy=lower_bound(ny+1,ny+my+1,sy)-ny; ex=lower_bound(nx+1,nx+mx+1,ex)-nx; ey=lower_bound(ny+1,ny+my+1,ey)-ny; for(int i=1;i<=mx;i++) for(int j=1;j<=my;j++) xx[i][j]+=xx[i][j-1]; for(int i=1;i<=my;i++) for(int j=1;j<=mx;j++) yy[i][j]+=yy[i][j-1]; for(int i=1;i<=mx;i++) for(int j=1;j<=my;j++) dis[i][j]=INF; // for(int i=1;i<=mx;i++) for(int j=1;j1) upd(x-1,y,now,yy[y][x-1],nx[x]-nx[x-1]); if(y>1) upd(x,y-1,now,xx[x][y-1],ny[y]-ny[y-1]); if(x