#include using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define rep(i,a,n) for(int i=(a);i<=(n);++i) #define dep(i,a,n) for(int i=(a);i>=(n);--i) #define eps 1e-8 #define pi 3.1415926535897 #define sqr(x) ((x)*(x)) #define MAX(a,b) a=max(a,b) #define MIN(a,b) a=min(a,b) #define SZ(x) ((int)(x).size()) #define CPY(a,b) memcpy(a,b,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define POSIN(x,y) (1<=(x)&&(x)<=n&&1<=(y)&&(y)<=m) #define all(x) (x).begin(),(x).end() #define COUT(S,x) cout< pii; typedef pair pll; typedef pair pff; typedef complex CD; const int inf=0x3f3f3f3f; const int mo=1000000007; inline void gn(long long&x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');c=='-'?(sg=-1,x=0):(x=c-'0'); while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';x*=sg; } inline void gn(int&x){long long t;gn(t);x=t;} inline void gn(unsigned long long&x){long long t;gn(t);x=t;} inline void gn(double&x){double t;scanf("%lf",&t);x=t;} inline void gn(long double&x){double t;scanf("%lf",&t);x=t;} templateinline void gn(T1&r,T2&s){gn(r),gn(s);} templateinline void gn(T1&r,T2&s,T3&t){gn(r),gn(s),gn(t);} templateinline void gn(T1&r,T2&s,T3&t,T4&u){gn(r),gn(s),gn(t),gn(u);} inline void gs(char *s){scanf("%s",s);} inline void gc(char &c){while((c=getchar())>126 || c<33);} inline void pc(char c){putchar(c);} const int DX[]={1,0,-1,0},DY[]={0,1,0,-1}; ll powmod(ll a,ll b) {ll res=1;a%=mo;for(;b;b>>=1){if(b&1)res=res*a%mo;a=a*a%mo;}return res;} ll powmod(ll a,ll b,ll mo) {ll res=1;a%=mo;for(;b;b>>=1){if(b&1)res=res*a%mo;a=a*a%mo;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} //******************************************* const int N=111111,M=555; int l,m,n,t,C; struct P{ int x,y; P(){} P(int a,int b):x(a),y(b){} }; pair a[N]; P st,en; mapMx,My; int px[N],py[N]; int v1[M][M],v2[M][M]; lf dis[M][M]; int vis[M][M]; lf len(int x,int y,int xx,int yy){ // printf("%d %d %d %d %d %d %d %d\n",x,y,xx,yy,px[x],py[y],px[xx],py[yy]); lf ans=0; if(x==xx)ans=1.0*abs(py[yy]-py[y])/v2[min(x,xx)][min(y,yy)]; else ans=1.0*abs(px[xx]-px[x])/v1[min(x,xx)][min(y,yy)]; return ans; } int main(){ #ifdef LOCAL freopen("C.in","r",stdin);//freopen("C.out","w",stdout); #endif scanf("%d",&C);rep(_,1,C){ Mx.clear();My.clear(); scanf("%d",&n); rep(i,1,n){ scanf("%d%d%d%d",&a[i].X.x,&a[i].X.y,&a[i].Y.x,&a[i].Y.y); Mx[a[i].X.x]=1; Mx[a[i].Y.x]=1; My[a[i].X.y]=1; My[a[i].Y.y]=1; } scanf("%d%d",&st.x,&st.y);Mx[st.x]=1;My[st.y]=1; scanf("%d%d",&en.x,&en.y);Mx[en.x]=1;My[en.y]=1; int xtot=0; for(auto &i:Mx)px[++xtot]=i.X,i.Y=xtot; int ytot=0; for(auto &i:My)py[++ytot]=i.X,i.Y=ytot; rep(i,1,n)a[i].X.x=Mx[a[i].X.x]; rep(i,1,n)a[i].X.y=My[a[i].X.y]; rep(i,1,n)a[i].Y.x=Mx[a[i].Y.x]; rep(i,1,n)a[i].Y.y=My[a[i].Y.y]; st=P(Mx[st.x],My[st.y]); en=P(Mx[en.x],My[en.y]); rep(i,0,xtot+1)rep(j,0,ytot+1)v1[i][j]=v2[i][j]=1,dis[i][j]=1e30,vis[i][j]=0; rep(i,1,n)rep(j,a[i].X.x,a[i].Y.x-1)rep(k,a[i].X.y,a[i].Y.y)v1[j][k]++; rep(i,1,n)rep(j,a[i].X.x,a[i].Y.x)rep(k,a[i].X.y,a[i].Y.y-1)v2[j][k]++; // rep(i,1,n)val[a[i].X.x][a[i].X.y]++; // rep(i,1,n)val[a[i].Y.x+1][a[i].Y.y+1]++; // rep(i,1,n)val[a[i].X.x][a[i].Y.y+1]--; // rep(i,1,n)val[a[i].Y.x+1][a[i].X.y]--; // rep(i,1,xtot)rep(j,1,ytot)val[i][j]-=val[i-1][j-1]-val[i-1][j]-val[i][j-1]; set >S; dis[st.x][st.y]=0; S.insert(mp(0,mp(st.x,st.y))); // rep(i,1,n)printf("%d %d %d %d\n",a[i].X.x,a[i].X.y,a[i].Y.x,a[i].Y.y); // rep(i,1,xtot){rep(j,1,ytot)printf("%d ",val[i][j]);puts("");} // printf("%d %d %d %d\n",st.x,st.y,en.x,en.y); while(!S.empty()){ auto k=*(S.begin());S.erase(S.begin()); int x=k.Y.X,y=k.Y.Y;vis[x][y]=1; // printf("%d %d %.9lf\n",x,y,dis[x][y]); rep(k,0,3){ int xx=x+DX[k],yy=y+DY[k]; if(1<=xx&&xx<=xtot&&1<=yy&&yy<=ytot&&!vis[xx][yy]&&dis[xx][yy]>dis[x][y]+len(x,y,xx,yy)){ S.erase(mp(dis[xx][yy],mp(xx,yy))); dis[xx][yy]=dis[x][y]+len(x,y,xx,yy); S.insert(mp(dis[xx][yy],mp(xx,yy))); } } } printf("%.5lf\n",dis[en.x][en.y]); } return 0; }