|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
You are competing with another company for a city contract to fill potholes in the city streets.
The city has set up a contest in which you will compete in a rectangular parking lot containing a large number of potholes to see which company can work faster.
You are to stretch a rope from one end of the lot to the other, dividing the lot into two rectangles. Your opponent will then choose which side of the lot they wish to work in, while you work in the other side. Obviously, then, you need to try can divide the lot so that the amount of work to be done (total area of all potholes) on each side is as nearly equal as possible.
For the purposes of this problem, potholes will be modeled as circles. Potholes do not overlap one another or the edges of the parking lot. Your chosen placement of the rope may not cross a pothole. Potholes may, however, be tangent to one another, to the edges of the lot, or to the rope.
Input consists of one or more problem sets. Each problem set consists of
Write a program that, given a description of the parking lot and of the potholes, determines where to place to rope so that the total area of the potholes on each side of the rope is as nearly equal as possible. Potholes will be modeled as perfect circles. The rope may not pass through any pothole, though it may be tangent to potholes.
For each problem set, print a line
x1 y1 x2 y2
where (x1, y1) and (x2, y2) are the points where the rope crosses the boundary of the parking lot. Order your output so that x1 ≤ x2 and y1 ≤ y2. Point coordinates should be printed to one decimal place accuracy.
These points should be chosen so as to most nearly divide the set of potholes into two equal sets by total area.
If there is more than one possible placement of the rope that achieves the most nearly equal divisions of pothole areas, choose the placement that most nearly divides the parking lot into equal areas. If this does not resolve the tie, favor the placement of the rope that intersects the x axis of the lot. Any remaining ties should be broken in favor of the smaller x value.
16.0 12.0 1.0 1.0 0.8 8.0 6.0 2.0 3.0 5.0 1.0 3.0 9.0 1.0 0 0 0 0 0
6.0 0.0 6.0 12.0