Azshara's deep sea

As a little Gnome Rogue, WW is a loyal player in World of Warcraft. Although the daily tasks of version 8.2 are so boring, he insists on going online every day.

Since the stealth skill of the Rogue can prevent him from being seen by the enemy, he always plays PVP in the wild. One night, on the way finding an elite monster on the map, he saw a shivering priest who is chased by the Rogue and a Demon Hunter. Then he decided to help the poor priest. Sure enough, with the helping of the most powerful specialization in the current version, the priest TT survived.

WW made friends with TT. In the conversation, WW found that the guild that TT takes part is preparing to raid the epic mode of the Dungeon ‘Eternal Palace’. As a core member of the union team, TT is worried with the last BOSS of the Dungeon.

According to Dungeon’s Guide, the last BOSS Azshara will enter a hidden phase when her HP drops to 0%. At this time, the previous battlefield will be destroyed and all players will sink into a deep sea. The BOSS will strengthen to become the Azshara’s soul.

Players need to fight within the range of the lights. The lights are tied to the wooden sticks. Therefore, we can assume that the player is fighting in a convex polygon made by wooden sticks.(The wooden sticks are distributed over the entire polygon.) Of course, players can not only stand on the wooden sticks, but also move freely within this area.

Azshara’s souls has a skill to deliver stingers to the crowd in the battlefield. Each stinger would make a circle whose radius is R. Another skill of Azshara’s soul is to choose two players randomly (Two players are a pair, and any two pairs do not contain the same person) and link them with an ice ray. If the ice ray passes through the circle formed by the stinger ( Including the case where the ray is tangent to the circle ) , all of the players will die. So we can’t let the rays pass through these circles. There are some other requirements for the ice ray technique: 1. Two ice rays cannot intersect. (Ray intersection does not include the coincidence of endpoints of two different segments) 2. The two choosen players cannot be too close.

Eventually, the leader comes up with such a way to help players win this boss faster:

First, in order to influence other players that are not selected as small as possible, the selected players should stand at the outermost side of the battlefield.

Second, in order to find the position more accurately, the player needs to run to the outermost wooden sticks, that is, the coordinates (x,y) of the wooden sticks are the coordinates (x,y) of the player (a wooden stick can withstand multiple players).

Third, players in the same pair cannot stand on adjacent wooden sticks. In other words, if we number the outermost wooden sticks, the players in the same pair cannot have one person in the position of i and the other person in the position of i+1.

The leader now knows the position of the wooden sticks and the position of the center of the circle. What is the maximum number of the pairs he can arrange in the battlefield?

The input includes several cases. The first line of input is a single line of integer T (1≤T≤10), the number of test cases.

For each case, the first line contains three space-separated integers: N(0<=N<=400), G(0 <= G <= 100) , and R (0<=R<=100)

Next there will be N lines. Each line contains two space-separated integers x,y that are the position of wooden sticks.

Next there will be G lines. Each line contains two space-separated integers x,y that are the position of stingers inside battlefield.

0<=x,y<=1e6

Only one line includes a number indicating how many pairs of players can be arranged in the battlefield.

2
5 3 1
6 10
10 7
9 1
2 0
0 3
2 2
5 6
8 3
5 0 0
1 1
2 1
3 2
1 3
0 2

1
2

2019 Multi-University Training Contest 3