Oh No!!! The predator has entered the room again. But thistime it is a different kind of room.

The room is a square of size10000 X 10000. There are several compartments of different shapes and sizes,situated strictly inside the room. The walls of different compartments don’toverlap, but a compartment can be completely inside that of another.

This time the predator haslearned to hop over walls, but it can jump over at most one wall at a time.Given the starting and ending coordinates of the predator, and the positions ofthe compartments, your job is to find out the minimum number of hops requiredfor the predator to reach his destination from the start.

The starting and ending positionsare never on the boundary of any compartment.

Input

The first line of input is aninteger (T ≤ 20), that indicates the number of test cases. Eachcase starts with an integer

(n ≤ 20), thatdetermines the number of compartments in the room. The next n lines give the positions of thecompartments. The compartments are simple polygons. The description of eachcompartment starts with an integers (S ≤ 10), that gives the numberof sides of the polygon, followed by S pairsof x, y coordinates in order. Nextthere is an integer Q thatdetermines the number of queries for this scenario. Each of the next Q lines contains 4 integers x1, y1, x2, y2. (x1, y1) is the starting position and (x2, y2) is the ending position.

The lower left and upper rightcoordinates of the room are (0, 0) and (10000, 10000) respectively.

Output

For each case, output the casenumber. Then for each query, output the minimum number of hops required.

ProblemSetter: Sohel Hafiz

Next Generation Contest 2

Illustration

The following diagram depicts the first sample input.

Pink spot à starting position

Black spot à target

The three hops are shown by three broad line segments.

利用射線法 - 判斷一個點是不是在一個簡單多邊形內。
判斷的方法 從那個點拉一條水平射線, 求交到多邊形的點個數。
偶數在多邊形外，奇數則在多邊內。 (核心代碼來自 DJWS)

然後利用這個方法，建出這棵關係樹。
然後求最短路徑。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
using namespace std;
vector<int> g[30];
int bg[30][30];
int used[30];
struct Pt {
    double x, y;
};
struct Polygon {
    Pt p[20];
    int n;
};
Polygon ply[30];
int parent[30];
int inPolygon(Pt p[], Pt q, int n) {
    int i, j, k = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y)+p[i].x)
           k++;
    }
    return k&1;
}
void build(int nd, int n) {
    int i, j;
    for(i = 0; i <= n; i++) {
        if(used[i] == 0 && inPolygon(ply[nd].p, ply[i].p[0], ply[nd].n)) {
            for(j = 0; j <= n; j++)
                if(i != j && used[j] == 0 && inPolygon(ply[j].p, ply[i].p[0], ply[j].n))
                    break;
            if(j == n+1) {
                used[i] = 1;
                parent[i] = nd;
                g[nd].push_back(i);
                bg[i][nd] = bg[nd][i] = 1;
                build(i, n);
            }
        }
    }
}
int treefind(int nd, Pt p) {
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        if(inPolygon(ply[*it].p, p, ply[*it].n)) {
            return treefind(*it, p);
        }
    }
    return nd;
}
int main() {
    int t, n, cases = 0;
    int i, j, k;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%d", &ply[i].n);
            for(j = 0; j < ply[i].n; j++)
                scanf("%lf %lf", &ply[i].p[j].x, &ply[i].p[j].y);
        }
        ply[i].n = 4;
        ply[i].p[0].x = -1, ply[i].p[0].y = -1;
        ply[i].p[1].x = -1, ply[i].p[1].y = 10005;
        ply[i].p[2].x = 10005, ply[i].p[2].y = 10005;
        ply[i].p[3].x = 10005, ply[i].p[3].y = -1;
        for(i = 0; i <= n; i++)
            g[i].clear(), used[i] = 0;
        for(i = 0; i <= n; i++) {
            for(j = 0; j <= n; j++)
                bg[i][j] = 0xffff; // oo
            bg[i][i] = 0;
        }
        used[n] = 1;
        build(n, n);
        for(k = 0; k <= n; k++)
            for(i = 0; i <= n; i++)
                for(j = 0; j <= n; j++)
                    if(bg[i][j] > bg[i][k]+bg[k][j])
                        bg[i][j] = bg[i][k]+bg[k][j];
        int Q;
        printf("Case %d:\n", ++cases);
        scanf("%d", &Q);
        while(Q--) {
            Pt st, ed;
            scanf("%lf %lf", &st.x, &st.y);
            scanf("%lf %lf", &ed.x, &ed.y);
            int stp = treefind(n, st);
            int edp = treefind(n, ed);
            printf("%d\n", bg[stp][edp]);
        }
    }
    return 0;
}