#include #include #include #include #include #include #define maxn 205 #define inf 999999999999999 using namespace std; typedef long long ll; int read() { int x=0,f=1; char ch=getchar(); while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();} while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n; struct P{ int x1,x2,y1,y2; }re[maxn]; int a[maxn*2],b[maxn*2],cnt1,cnt2; double disx[maxn*2][maxn*2],disy[maxn*2][maxn*2]; int stx,sty,enx,eny; int id[maxn*2][maxn*2]; int head[maxn*maxn*4],nxt[maxn*maxn*20],to[maxn*maxn*20],tot; double c[maxn*maxn*20]; void add(int u,int v,double x) { tot++; nxt[tot]=head[u]; head[u]=tot; to[tot]=v; c[tot]=x; } struct X{ int id; double dis; }; struct cmp{ bool operator () (const X a,const X b){ return a.dis>b.dis; } }; double dis[maxn*maxn*4]; priority_queue,cmp>q; int book[maxn*maxn*4]; void dijkstra() { memset(book,0,sizeof(book)); for(int i=1;i<=cnt1*cnt2;i++) dis[i]=inf; dis[id[stx][sty]]=0; q.push((X){id[stx][sty],0}); while(q.size()) { int now=q.top().id; q.pop(); if(book[now]) continue; book[now]=1; for(int i=head[now];i;i=nxt[i]) { if(dis[to[i]]>dis[now]+c[i]) { dis[to[i]]=dis[now]+c[i]; q.push((X){to[i],dis[to[i]]}); } } } printf("%.5lf\n",dis[id[enx][eny]]); } int main() { T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++) re[i].x1=read(),re[i].y1=read(),re[i].x2=read(),re[i].y2=read(); cnt1=cnt2=0; for(int i=1;i<=n;i++) { a[++cnt1]=re[i].x1;a[++cnt1]=re[i].x2; b[++cnt2]=re[i].y1;b[++cnt2]=re[i].y2; } stx=read();sty=read();enx=read();eny=read(); a[++cnt1]=stx;a[++cnt1]=enx; b[++cnt2]=sty;b[++cnt2]=eny; sort(a+1,a+cnt1+1);cnt1=unique(a+1,a+cnt1+1)-a-1; sort(b+1,b+cnt2+1);cnt2=unique(b+1,b+cnt2+1)-b-1; for(int i=1;i<=n;i++) { re[i].x1=lower_bound(a+1,a+cnt1+1,re[i].x1)-a; re[i].x2=lower_bound(a+1,a+cnt1+1,re[i].x2)-a; re[i].y1=lower_bound(b+1,b+cnt2+1,re[i].y1)-b; re[i].y2=lower_bound(b+1,b+cnt2+1,re[i].y2)-b; } enx=lower_bound(a+1,a+cnt1+1,enx)-a; eny=lower_bound(b+1,b+cnt2+1,eny)-b; stx=lower_bound(a+1,a+cnt1+1,stx)-a; sty=lower_bound(b+1,b+cnt2+1,sty)-b; memset(disx,0,sizeof(disx)); memset(disy,0,sizeof(disy)); for(int i=1;i<=n;i++) { for(int j=re[i].x1;j<=re[i].x2-1;j++) disx[j][re[i].y1]+=1,disx[j][re[i].y2+1]-=1; for(int j=re[i].x1;j<=re[i].x2;j++) disy[j][re[i].y1]+=1,disy[j][re[i].y2]-=1; } for(int i=1;i<=cnt1-1;i++) for(int j=1;j<=cnt2;j++) disx[i][j]+=disx[i][j-1]; for(int i=1;i<=cnt1;i++) for(int j=1;j<=cnt2-1;j++) disy[i][j]+=disy[i][j-1]; for(int i=1;i<=cnt1-1;i++) for(int j=1;j<=cnt2;j++) disx[i][j]=(double)(a[i+1]-a[i])/(disx[i][j]+1); for(int i=1;i<=cnt1;i++) for(int j=1;j<=cnt2-1;j++) disy[i][j]=(double)(b[j+1]-b[j])/(disy[i][j]+1); for(int i=1;i<=cnt1;i++) for(int j=1;j<=cnt2;j++) id[i][j]=(i-1)*cnt2+j; memset(head,0,sizeof(head)); tot=0; for(int i=1;i<=cnt1-1;i++) for(int j=1;j<=cnt2;j++) add(id[i][j],id[i+1][j],disx[i][j]),add(id[i+1][j],id[i][j],disx[i][j]); for(int i=1;i<=cnt1;i++) for(int j=1;j<=cnt2-1;j++) add(id[i][j],id[i][j+1],disy[i][j]),add(id[i][j+1],id[i][j],disy[i][j]); dijkstra(); } return 0; }