UVa11030-Predator II

Problem D

Predator II

Time limit: 2 seconds

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

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

This time the predator has learned 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 of the compartments, your job is to find out the minimum number of hops required for the predator to reach his destination from the start.

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

Input

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

(n ≤ 20), that determines the number of compartments in the room. The next n lines give the positions of the compartments. The compartments are simple polygons. The description of each compartment starts with an integers (S ≤ 10), that gives the number of sides of the polygon, followed by S pairs of x, y coordinates in order. Next there is an integer Q that determines 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 right coordinates of the room are (0, 0) and (10000, 10000) respectively.

Output

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

Sample Input

Output for Sample Input

2

3

4 1 1 5 1 5 5 1 5

4 2 2 4 2 4 4 2 4

3 7 7 10 10 7 10

1

3 3 8 9

1

4 1 1 10 1 10 10 1 10

2

2 2 100 100

100 100 2 2

Case 1:

3

Case 2:

1

1

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.

題目大意就是有 n個polygon， m組詢問，每次詢問一個點最少要越過多少條邊才能到達另一個點， 用容斥可以解決 包括a點的polygon數量+b點的polygon數量-2*（同時包括a,b的polygon數量）

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include #include #include #include #include #include #include #include using namespace std; const double eps = 1e-8; struct Point{ double x,y; friend bool operator < (Point a,Point b){ if(fabs(a.x-b.x)>eps) return a.x < b.x; else return a.y < b.y; } friend bool operator == (Point a,Point b){ return fabs(a.x-b.x) 0) return 1; else return -1; } double det(Point p1,Point p2){ return p1.x*p2.y-p1.y*p2.x; } int inPolygon(vector p, Point q) { int cnt = 0; int n = p.size(); for(int 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) cnt++; } return cnt&1; } int n; vector > vp; int main(){ int ncase,T=1; cin >> ncase; while(ncase--){ cin >> n; vp.clear(); for(int i = 0; i < n; i++){ vector t; t.clear(); int m; cin >> m; for(int k = 0; k < m; k++){ double x,y; cin >> x >> y; t.push_back(Point(x,y)); } vp.push_back(t); } int fd; cin >> fd; printf("Case %d:\n",T++); while(fd--){ int a=0,b=0,c=0; double x,y; cin >> x >> y; Point t1(x,y); cin >> x >> y; Point t2(x,y); for(int i = 0; i < n; i++){ int flag1 = inPolygon(vp[i],t1),flag2 = inPolygon(vp[i],t2); if(flag1) a++; if(flag2) b++; if(flag1&&flag2) c++; } cout<