All Tracks>Math> Geometry> Line Sweep Technique> Problem
Simple Polygons
★★★★★

5

2 votes
Geometry, Line Sweep Technique, Math, Medium
Problem

Given n simple polygons, no two polygons has common points but one polygon can strictly be inside the other. You are asked to answer q queries of two kinds:

1 x y: add a point at position (x, y).

2 u: output the number of points inside or on boundary of u-th polygon.

Input Format

The first line of input contains a single integer T, denoting the number of test cases.

Each test case is described as follow: a single line contains an integer n, denoting the number of polygons, each polygon begins with an integer k, denoting the number of vertices, each of k following lines contains two space-seperated integers x y, denoting coordinates of its vertices. The next line contains an integer q, denoting the number of queries. Each queries is described as above.

Output Format

For each query, output a single line contains the answer.

Constraints

  • 1 ≤ T ≤ 5
  • 1 ≤ n, q ≤ 105
  • 1 ≤ sum of vertices of all polygons overall test cases ≤ 106
  • 0 ≤ all coordinates ≤ 108
  • 1 ≤ u ≤ n

 

Sample Input
1
4
9
1 1
7 0
10 1
12 6
12 0
14 7
7 8
2 7
1 5
5
3 3
4 4
3 5
4 6
2 6
7
6 1
10 3
8 4
10 6
7 7
6 5
5 4
6
13 1
15 1
16 2
17 1
17 4
15 5
20
1 3 4
2 2
1 5 7
2 2
2 1
1 7 3
2 1
2 2
2 3
1 11 3
1 10 8
1 13 4
2 1
2 2
2 3
1 14 2
2 1
2 2
2 3
2 4
Sample Output
1
1
2
3
1
1
4
1
1
4
1
1
1
Time Limit: 4
Memory Limit: 512
Source Limit:
Explanation

enter image description here

Contributers:
Editor Image

?