Hide

Problem AU
Fancy Fence (easy)

/problems/fancyeasy/file/statement/en/img-0001.jpg
Photo by DBduo Photograpy from Flickr
Note that this is an easier version of the problem fancy

Oskar really loves onions. Unfortunately, the onions he loves belong to the local vegetable farmer, Lökas Tomatcek. Since Oskar is very cheap, he simply steals Lökas’ onions from the large, convex, onion field. For obvious reasons, Lökas does not approve of this. Rather than going to the police, however, Lökas wants to raise a high-energy laser fence around the onions to replace his wooden fence.

As laser fences are rather expensive, Lökas can only afford to upgrade $K$ of the fence posts to laser fence posts. If a set of posts are upgraded, the lasers will protect all the onions lying strictly within the convex hull of the selected fence posts. This may not be all of the onions though. Lökas wonders which posts he should upgrade if he wants to protect as many of his $N$ onions as possible.

The original fence has the shape of a convex polygon with $M$ fence posts as vertices, and all the onions lie strictly within the fence.

Input

The first line of input consists of three space-separated integers $3 \le N \le 1\, 000$, $3 \le M \le 100$ and $3 \le K \le 100$. These are the number of onions, the number of old fence posts, and the number of fence posts Lökas can upgrade.

Then follow $N$ lines with two space-separated integers $0 \le X_ i, Y_ i \le 10^9$ each. $(X_ i, Y_ i)$ gives the coordinate of the $i$-th onion.

Then follow $M$ lines with two space-separated integers $0 \le A_ i, B_ i \le 10^9$ each. $(A_ i, B_ i)$ gives the coordinate of the $i$-th fence post.

The fence posts will be given in clockwise order of the old fence. No three fence posts will lie on a line.

Output

Output should be a single integer; the maximum number of onions Lökas can protect.

Sample Input 1 Sample Output 1
3 5 3
1 1
2 2
1 3
0 0
0 3
1 4
3 3
3 0
2
Sample Input 2 Sample Output 2
5 6 4
3 5
5 5
4 4
7 2
5 2
6 1
4 2
2 6
5 6
8 3
8 2
4

Please log in to submit a solution to this problem

Log in