BILFAR - Bill of Fare


Given a large polygon dining table (not always a simple polygon) with the following properties :

- there is no intersecting area (ex : area A)
- there is no space inside the polygon (ex : area B)
- there is no 3 edges that are concurrent (ex : point C)
- every nodes are not lying on any edge except 2 edges that connect that node with 2 other nodes (ex : point D)
- every nodes forming a convex corner because a table with concave corner is an uncomfortable table (ex : point E)

Example of invalid table :



Given also M dishes with the following rules :

- placed on the table
- not on the edge of the table
- there is no pair of different food that have the same place

You have to answer Q queries :

- each query identified by L and R
- the query is "what is the minimum moves in order to make some dishes (from L-th dish to R-th dish inclusive) placed in same region ?"
- queries are independent

Notes :

- two dishes are considered in same region if and only if from one dish can be slid to another one without crossing any edge
- one move is to slide a dish to another region through an edge
- every dishes should be still on the table, but they may lie on the edge

Explanation :




- dish A is valid because it placed on the table
- dish C is invalid because it placed on the edge
- dish E is invalid because it placed outside the table
- sliding from dish A to dish B is considered as one move
- dish B and dish D is considered as one region
- dish F is invalid because it placed exactly on dish D

Input and output format :

- An integer T represent the number of test case, each test case :
- First line contains 3 separated integer N, M, and Q
- Next N lines contain Xi and Yi represent the coordinate of i-th node
- Next M lines contain Pi and Qi represent the coordinate of i-th dish
- Next Q lines contain Li and Ri represent the parameter of i-th query
- You should output Q lines contain the answers of those queries

Constraints :

- 1 <= T <= 10
- 3 <= N <= 1000
- 2 <= M <= 1000
- 1 <= Q <= 1000
- 0 <= Xi, Yi <= 10^9
- 0 < Pi, Qi < 10^9
- 1 <= Li < Ri <= M

Sample input :

1
7 5 3
1 1
1 5
5 1
7 2
7 8
9 5
5 5
6 2
2 3
5 4
8 6
5 3
1 5
2 4
3 5

Sample output :

2
2
1

 

Explanation of sample :



- query 1 : we can slide 2-nd dish and 4-th dish to the middle region
- query 2 : using the same way as query 1
- query 3 : prefer sliding 4-th dish (1 move) rather than sliding 3-rd and 5-th dishes (2 moves)



Added by:Amnu
Date:2019-02-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All