#include using namespace std; int t, n; int xa[10020]; int xb[10020]; int ya[10020]; int yb[10020]; int xs, ys, xe, ye; int xx[100020], xc; int yy[100020], yc; int ax[420][420]; int ay[420][420]; vector > a[200020]; double d[200020]; int main() { scanf("%d", &t); for (int tt = 0; tt < t; tt++) { scanf("%d", &n); xc = yc = 0; memset(ax, 0, sizeof ax); memset(ay, 0, sizeof ay); for (int i = 0; i < n; i++) { scanf("%d%d%d%d", &xa[i], &ya[i], &xb[i], &yb[i]); xx[xc++] = xa[i]; xx[xc++] = xb[i]; yy[yc++] = ya[i]; yy[yc++] = yb[i]; } scanf("%d%d%d%d", &xs, &ys, &xe, &ye); // printf("%d %d %d %d\n", xs, ys, xe, ye); xx[xc++] = xs; xx[xc++] = xe; yy[yc++] = ys; yy[yc++] = ye; sort(xx, xx + xc); sort(yy, yy + yc); xc = unique(xx, xx + xc) - xx; yc = unique(yy, yy + yc) - yy; for (int i = 0; i < xc * yc; i++) { a[i].clear(); } for (int i = 0; i < n; i++) { xa[i] = lower_bound(xx, xx + xc, xa[i]) - xx; xb[i] = lower_bound(xx, xx + xc, xb[i]) - xx; ya[i] = lower_bound(yy, yy + yc, ya[i]) - yy; yb[i] = lower_bound(yy, yy + yc, yb[i]) - yy; } xs = lower_bound(xx, xx + xc, xs) - xx; xe = lower_bound(xx, xx + xc, xe) - xx; ys = lower_bound(yy, yy + yc, ys) - yy; ye = lower_bound(yy, yy + yc, ye) - yy; // printf("%d %d %d %d\n", xs, ys, xe, ye); for (int i = 0; i < n; i++) { for (int j = xa[i]; j < xb[i]; j++) { for (int k = ya[i]; k <= yb[i]; k++) { ax[j][k]++; } } for (int j = xa[i]; j <= xb[i]; j++) { for (int k = ya[i]; k < yb[i]; k++) { ay[j][k]++; } } } for (int i = 0; i < xc; i++) { for (int j = 0; j < yc - 1; j++) { a[i * yc + j].push_back(make_pair(i * yc + j + 1, (yy[j + 1] - yy[j]) / (ay[i][j] + 1.0))); a[i * yc + j + 1].push_back(make_pair(i * yc + j, (yy[j + 1] - yy[j]) / (ay[i][j] + 1.0))); // printf("%d %d %.6f\n", i * yc + j, i * yc + j + 1, (yy[j + 1] - yy[j]) / (ay[i][j] + 1.0)); } } for (int i = 0; i < xc - 1; i++) { for (int j = 0; j < yc; j++) { a[i * yc + j].push_back(make_pair(i * yc + j + yc, (xx[i + 1] - xx[i]) / (ax[i][j] + 1.0))); a[i * yc + j + yc].push_back(make_pair(i * yc + j, (xx[i + 1] - xx[i]) / (ax[i][j] + 1.0))); // printf("%d %d %.6f\n", i * yc + j, i * yc + j + yc, (xx[i + 1] - xx[i]) / (ax[i][j] + 1.0)); } } for (int i = 0; i < xc * yc; i++) { d[i] = 1e30; } priority_queue > q; d[xs * yc + ys] = 0; q.push(make_pair(-d[xs * yc + ys], xs * yc + ys)); while (q.size() > 0) { pair u = q.top(); q.pop(); if (-u.first > d[u.second]) { continue; } // printf("%.6f %d\n", u.first, u.second, d[u.second]); for (int i = 0; i < a[u.second].size(); i++) { pair e = a[u.second][i]; if (d[e.first] > d[u.second] + e.second) { // printf("%.6f %.6f %.6f\n", d[e.first], d[u.second] + e.second, e.second); d[e.first] = d[u.second] + e.second; q.push(make_pair(-d[e.first], e.first)); } } } // printf("%d %d %d %d\n", xs, ys, xe, ye); printf("%.5f\n", d[xe * yc + ye]); } return 0; }