#include <cstdio>#include <cstring>#include <map>#include <cmath>#include <vector>#include <algorithm>#define MAXM 200#define MAXN 25000#define INF 2147483647using namespace std;struct node{ int x, y;} nod[MAXN];struct edg{ int l, r; bool dir;} ee[MAXM];struct edge{ int to, d, next;} e[1000000];map <pair<int, int>, int> ID;map <pair<int, int>, int> ::iterator p;int M, N;int head[MAXN];int dist[MAXN];bool mk[MAXN];void Add_Edge(int u, int v, int va, int &top){ e[++top].to = v, e[top].d = va, e[top].next = head[u], head[u] = top;}bool check(int a, int b, int c){ return (a <= c && b >= c);}bool cmpy(int a, int b){ return nod[a].y < nod[b].y;}bool cmpx(int a, int b){ return nod[a].x < nod[b].x;}void build_G(int st, int ed){ int tmp[MAXN]; int top = -1; memset(head, -1, sizeof (head)); for (int i = 0; i < M; ++i) { if (ee[i].dir) { int x = nod[ee[i].l].x; int y1 = nod[ee[i].l].y; int y2 = nod[ee[i].r].y; int cnt = 0, u; tmp[cnt++] = ee[i].l; if (nod[st].x == x && check(y1, y2, nod[st].y)) tmp[cnt++] = st; if (nod[ed].x == x && check(y1, y2, nod[ed].y)) tmp[cnt++] = ed; for (int j = 0; j < M; ++j) if (!ee[j].dir) { if (check(nod[ee[j].l].x, nod[ee[j].r].x, x) && check(y1, y2, nod[ee[j].l].y)) { p = ID.find(make_pair(x, nod[ee[j].l].y)); if (p == ID.end()) { ID.insert(make_pair(make_pair(x, nod[ee[j].l].y), N)); u = N++; nod[u].x = x, nod[u].y = nod[ee[j].l].y; } else u = p->second; tmp[cnt++] = u; } } tmp[cnt++] = ee[i].r; sort(tmp, tmp + cnt, cmpy); for (int j = 1; j < cnt; ++j) if (nod[tmp[j]].y > nod[tmp[j - 1]].y) { int d = nod[tmp[j]].y - nod[tmp[j - 1]].y; Add_Edge(tmp[j], tmp[j - 1], d, top); Add_Edge(tmp[j - 1], tmp[j], d, top); } } else { int y = nod[ee[i].l].y; int x1 = nod[ee[i].l].x; int x2 = nod[ee[i].r].x; int cnt = 0, u; tmp[cnt++] = ee[i].l; if (nod[st].y == y && check(x1, x2, nod[st].x)) tmp[cnt++] = st; if (nod[ed].y == y && check(x1, x2, nod[ed].x)) tmp[cnt++] = ed; for (int j = 0; j < M; ++j) if (ee[j].dir) { if (check(nod[ee[j].l].y, nod[ee[j].r].y, y) && check(x1, x2, nod[ee[j].l].x)) { p = ID.find(make_pair(nod[ee[j].l].x, y)); if (p == ID.end()) { ID.insert(make_pair(make_pair(nod[ee[j].l].x, y), N)); u = N++; nod[u].x = nod[ee[j].l].x, nod[u].y = y; } else u = p->second; tmp[cnt++] = u; } } tmp[cnt++] = ee[i].r; sort(tmp, tmp + cnt, cmpx); for (int j = 1; j < cnt; ++j) if (nod[tmp[j]].x > nod[tmp[j - 1]].x) { int d = nod[tmp[j]].x - nod[tmp[j - 1]].x; Add_Edge(tmp[j], tmp[j - 1], d, top); Add_Edge(tmp[j - 1], tmp[j], d, top); } } }}void dijkstra(int st, int ed){ for (int i = 0; i < N; ++i) dist[i] = INF; dist[st] = 0; memset(mk, 0, sizeof (mk)); for (int i = 0; i < N; ++i) { int u, mind = INF; for (int j = 0; j < N; ++j) if (!mk[j] && mind > dist[j]) { mind = dist[j]; u = j; } mk[u] = true; if (mk[ed]) break; for (int j = head[u]; j != -1; j = e[j].next) { int v = e[j].to; if (!mk[v]) { int tmp = dist[u] + e[j].d; if (tmp < dist[v]) dist[v] = tmp; } } }}void init(){ int cas; scanf("%d", &cas); for (int i = 1; i <= cas; ++i) { scanf("%d", &M); N = 0; ID.clear(); for (int j = 0; j < M; ++j) { int x1, x2, y1, y2, u, v; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); p = ID.find(make_pair(x1, y1)); if (p == ID.end()) { ID.insert(make_pair(make_pair(x1, y1), N)); u = N++; nod[u].x = x1, nod[u].y = y1; } else u = p->second; p = ID.find(make_pair(x2, y2)); if (p == ID.end()) { ID.insert(make_pair(make_pair(x2, y2), N)); v = N++; nod[v].x = x2, nod[v].y = y2; } else v = p->second; ee[j].l = u, ee[j].r = v, ee[j].dir = (x1 == x2); if (ee[j].dir && nod[u].y > nod[v].y) swap(ee[j].l, ee[j].r); if (!ee[j].dir && nod[u].x > nod[v].x) swap(ee[j].l, ee[j].r); } int x1, x2, y1, y2, st, ed; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); p = ID.find(make_pair(x1, y1)); if (p == ID.end()) { ID.insert(make_pair(make_pair(x1, y1), N)); st = N++; nod[st].x = x1, nod[st].y = y1; } else st = p->second; p = ID.find(make_pair(x2, y2)); if (p == ID.end()) { ID.insert(make_pair(make_pair(x2, y2), N)); ed = N++; nod[ed].x = x2, nod[ed].y = y2; } else ed = p->second; build_G(st, ed); dijkstra(st, ed); printf("Case %d:n", i); if (dist[ed] == INF) puts("-1"); else printf("%dn", dist[ed]); }}int main(){ init(); return 0;}
