#include #include #include #include #include #define il inline #define vd void typedef long long ll; il ll gi(){ ll x=0,f=1; char ch=getchar(); while(!isdigit(ch))f^=ch=='-',ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return f?x:-x; } int n,x1[210],x2[210],y1[210],y2[210],xa,xb,ya,yb,S,T; int ux[410],uy[410],mx,my; int H1[410][410],H2[410][410],num[410][410],cnt; int fir[170010],dis[4000010],nxt[4000010],id; double w[4000010],dist[170010]; bool vis[170010]; il vd _link(int a,int b,double c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;} il vd link(int a,int b,double c){ //printf("%d %d %.5lf\n",a,b,c); _link(a,b,c),_link(b,a,c); } std::priority_queue>que; int main(){ #ifdef XZZSB freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int qaq=gi(); while(qaq--){ memset(fir,0,sizeof fir); mx=my=0;id=0; int n=gi(); for(int i=1;i<=n;++i){ x1[i]=gi(),y1[i]=gi(),x2[i]=gi(),y2[i]=gi(); ux[++mx]=x1[i],ux[++mx]=x2[i]; uy[++my]=y1[i],uy[++my]=y2[i]; } xa=gi(),ya=gi(),xb=gi(),yb=gi(); ux[++mx]=xa,ux[++mx]=xb; uy[++my]=ya,uy[++my]=yb; std::sort(ux+1,ux+mx+1);mx=std::unique(ux+1,ux+mx+1)-ux-1; std::sort(uy+1,uy+my+1);my=std::unique(uy+1,uy+my+1)-uy-1; memset(H1,0,sizeof H1);memset(H2,0,sizeof H2); for(int i=1;i<=n;++i){ x1[i]=std::lower_bound(ux+1,ux+mx+1,x1[i])-ux; x2[i]=std::lower_bound(ux+1,ux+mx+1,x2[i])-ux; y1[i]=std::lower_bound(uy+1,uy+my+1,y1[i])-uy; y2[i]=std::lower_bound(uy+1,uy+my+1,y2[i])-uy; for(int x=x1[i];x<=x2[i];++x) for(int y=y1[i];y<=y2[i];++y) H1[x][y]+=xdist[x]+w[i]){ dist[dis[i]]=dist[x]+w[i]; que.push({-dist[dis[i]],dis[i]}); } while(!que.empty()&&vis[que.top().second])que.pop(); } printf("%.5lf\n",dist[T]); } return 0; }