2016 ACM ICPC South Central USA Regional Programming Contest
D - Cookie Cutting
You've decided to make some cookies for your sweetheart when she comes home from a long day of work. Mom always told you that food was the way to a woman's heart. Hopefully your sweetie will enjoy these cookies while you find a way to discuss how fixing the car might set your budget back a little bit next month.
Whilst preparing the sheet of cookie dough to cut shapes from, a presence can be sensed nearby. She thinks she's being sneaky, but you can hear your daughter giggling every time you turn your back!
The oven's alarm indicates it's preheated to the right temperature, but when you go to cut out the special shapes you wanted to make, you notice there are bites of cookie dough missing!
"Argh!!" you shout as you hear your daughter laughing her cookie-filled face all the way down the street as she goes to play with her friends.
Well it's time to put that computer science education to work. You'll need to know how many cookies you can get out of the remaining cookie dough so that you can figure out how much time you'll have to discuss money with your darling.
Good thing you can rearrange the cookie dough as many times as necessary to maximize the number of cookies you can make (keeping the dough at a constant thickness). The bites your daughter took may overlap, but all are fully contained within the bounds of the dough.
Input
The first line of input will contain the number of test cases, N (1 <= N <= 50). Each test case will begin with a W and H outlining the area of the cookie dough sheet, M number of bites, X and Y coordinates and radius R for the circular bites your daughter took, and a number S (3 <= S <= 100) lines giving the points defining the shape of the cookie, with A and B for the points.
Output
Your output should show ... how many cookies you can make! Use one line per test case output.
Sample Input
1 4.1 4.1 2 1.5 2 0.75 2.5 2 0.75 4 0 0 3 0 3 2 0 2
Sample Output
2