#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LOG(FMT...) fprintf(stderr, FMT) using namespace std; typedef long long ll; typedef unsigned long long ull; // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct Node { int x, y; double dis; Node(int x, int y, double dis) : x(x), y(y), dis(dis) {} bool operator>(const Node& rhs) const { return dis > rhs.dis; } }; const int N = 610; const double EPS = 1e-7; int n, xc, yc, ax, ay, bx, by; int cnt[N][N]; double dis[N][N]; bool vis[N][N]; double dx[N], dy[N]; void solve() { xc = yc = 0; scanf("%d", &n); vector, int> > modi; for (int i = 1; i <= n; ++i) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); modi.emplace_back(make_pair(x1, y1), 1); modi.emplace_back(make_pair(x1, y2 + EPS), -1); modi.emplace_back(make_pair(x2 + EPS, y1), -1); modi.emplace_back(make_pair(x2 + EPS, y2 + EPS), 1); dx[++xc] = x1; dx[++xc] = x2 + EPS; dx[++xc] = x2; dy[++yc] = y1; dy[++yc] = y2 + EPS; dy[++yc] = y2; } scanf("%d%d%d%d", &ax, &ay, &bx, &by); dx[++xc] = ax; dx[++xc] = bx; dy[++yc] = ay; dy[++yc] = by; sort(dx + 1, dx + xc + 1); xc = unique(dx + 1, dx + xc + 1) - dx - 1; sort(dy + 1, dy + yc + 1); yc = unique(dy + 1, dy + yc + 1) - dy - 1; for (int i = 1; i <= xc; ++i) fill(dis[i] + 1, dis[i] + yc + 1, 2e9 + 1); memset(cnt, 0, sizeof(cnt)); memset(vis, 0, sizeof(vis)); for (const auto& pr : modi) { double px, py; tie(px, py) = pr.first; int x = lower_bound(dx + 1, dx + xc + 1, px) - dx, y = lower_bound(dy + 1, dy + yc + 1, py) - dy; cnt[x][y] += pr.second; } for (int i = 1; i <= xc; ++i) for (int j = 1; j <= yc; ++j) cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1]; ax = lower_bound(dx + 1, dx + xc + 1, ax) - dx; bx = lower_bound(dx + 1, dx + xc + 1, bx) - dx; ay = lower_bound(dy + 1, dy + yc + 1, ay) - dy; by = lower_bound(dy + 1, dy + yc + 1, by) - dy; priority_queue, greater > q; q.push(Node(ax, ay, dis[ax][ay] = 0)); while (!q.empty()) { Node tmp = q.top(); q.pop(); int x = tmp.x, y = tmp.y; if (vis[x][y]) continue; vis[x][y] = true; if (x == bx && y == by) { printf("%.5f\n", tmp.dis); return; } function relax = [&](int X, int Y, double D) { if (dis[X][Y] > D) q.emplace(X, Y, dis[X][Y] = D); }; if (x > 1) relax(x - 1, y, tmp.dis + (dx[x] - dx[x - 1]) / (1 + cnt[x - 1][y])); if (y > 1) relax(x, y - 1, tmp.dis + (dy[y] - dy[y - 1]) / (1 + cnt[x][y - 1])); if (x < xc) relax(x + 1, y, tmp.dis + (dx[x + 1] - dx[x]) / (1 + cnt[x][y])); if (y < yc) relax(x, y + 1, tmp.dis + (dy[y + 1] - dy[y]) / (1 + cnt[x][y])); } } int main() { int t; scanf("%d", &t); while (t--) solve(); return 0; }