本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden ☆ before use]

1184. C. Lawn Maintenance


Description

George has been having trouble with his lawn. Not only does it seem to need fertilizing, but lately, he has found weeds popping up all over the place! Fortunately, the local home improvement store stocks a new version of a product, the improved Weed 'n Feed, that will fertilize grass and kill weeds at the same time. The product is sold in terms of 1000-squarefeet of coverage. George doesn't know how much grass he has, so he's having a difficult time trying to figure out how much \t\Teed 'n Feed to buy.
George does know a few things, though. George has the measurements of his lot, his house, and all of his landscaping beds that don't have grass. In order to figure out the area of his lawn, he needs to calculate the area of his lot, and subtract out the area of his house and landscaping beds.
Since George hates spending too much time/money, he's asked you to write a program that will help him figure out the optimum amount of fertilizer to buy. You'll have to calculate the area of his lawn, and then figure out hoyv many bags of fertilizer to buy (to cover the area) .
To make things simpler, the lot, house, and landscaping beds can all be described by simple (non self-intersecting) polygons (note that each polygon may be convex or concave).

Input

There will be multiple lawns to fertilize (George wants to share his program with the neighbors, too) . Input for each lawn begins with an integer L (3<=L <= 10), indicating the number of corners (vertices) on the lot. This is followed (on the same input line) by L pairs of integers, each pair specifying the X and Y coordinates of the position of each corner of the lot. The next input line for a data set will contain an integer H (3 <=H<= 10), indicating the number of corners (vertices) on the house. This is followed (on the same input line) by H pairs of integers, each pair specifying the X and Y coordinates of the position of each corner of the house. Following this will be an integer N on a line by itself, indicating the number of landscaping beds. Each of the next N lines will contain an integer B (3 <=B <=  10), indicating the number of corners (vertices) on that bed, followed by B pairs of integers, specifying the X and Y coordinates of the position of each corner.
All corners (vertices) will be specified consecutively in counter-clockwise order. Although vertices and edges may be shared, the house will be completely contained within the lot, and the landscaping beds will be completely contained within the lot and completely outside the house. Furthermore, the landscaping beds will not overlap each other, i.e., they won't have common area. You may also assume that the area of any polygon is always less than 231.
All coordinates will be separated by at least one space, and there may be leading spaces on each line (no trailing spaces). No characters other than digits, spaces, and new lines will appear in the input, i.e., no invalid input.
End of input is indicated by a value of zero for L (the number of vertices for a lot); this case should not be processed.

Output

For each lawn, print the number of fertilizer bags to buy. Use the following format:
Lawn #N: buy B bag(s)
where N is the number of the lawn (starting at 1), and B is the number of bags to buy. Note that the left-over fertilizer does not carry from one application (data set) to the next
application.
Leave a blank line after the output for each data set. Follow the format illustrated in Sample Output.

Samples

Input Copy
4
0 0 100 0 100 100 0 100
4 20 20 80 20 80 80 20 80
1
4 20 10 30 10 30 20 20 20
4 50 50 250 50 250 200 50 200
6 100 100 150 100 150 150 200 150 200 200 100 200
2
5 50 50 70 50 70 60 60 70 50 70
4 150 100 250 100 250 120 150 120
0
Output
Lawn #1: buy 7 bag(s)

Lawn #2: buy 21 bag(s)

Source

University of Central Florida Practice Local 2011
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1022. UCF 2011 Practice
My history solutions

You didn't submit any solution!
Submit your solution

Login Register