시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 192 | 21 | 17 | 10.759% |
You are about to plant a pair of fine kiwi trees inside your big property. You are worried that tree branches would grow beyond the boundaries of your property, making your neighbours complain. You must also avoid planting the two trees too close to each other so that the branches of the trees grow into each other, because that could lead to a loss of fruit.
The seller of the trees guaranteed that no branch or leaf will be farther than 4 meters from the trunk of its tree, thus we will model the trees as circles of radius 4 meters. The trunks are perfectly vertical.
Local government regulations forbid certain shapes of properties. In particular, in order for government employees to be able to draw and handle maps of the area, each property must satisfy the following properties:
Non-convex properties are allowed as long as the angles of consecutive sides follow rule 3 above, so the inner angle at a vertex can also be between 360 − 144 = 216 and 360 − 18 = 342 degrees. See Figure K.1 for an example.
Figure K.1: Illustration of Sample Input 1 and the solution given in Sample Output 1. All the marked angles are at least 18 and at most 144 degrees.
Your property follows these rules. Can you plant two trees inside the property such that their branches and leaves do not grow beyond its boundary, and that the branches and leaves of each tree do not grow into the other tree?
The input consists of:
Also, each polygon side is at least 30 meters (30 000 millimeters) long and the angle of two segments at a vertex is at least 18 degrees and at most 144 degrees. The polygon is nonintersecting and closed, i.e. the last vertex is connected to the first vertex.
If it is possible to plant two trees without their branches growing beyond the boundary of your property or into each other, output two lines, each containing two real numbers x and y giving the coordinates in millimeters of two points where the trees can be planted.
Otherwise, print “impossible”.
You may assume that increasing or decreasing the radius by 1 mm will not change whether or not it is possible to plant the trees. Your answer will be accepted if the tree locations are at least 3999 mm away from the boundary and at least 2 · 3999 mm away from each other.
4 0 3000 29000 38000 56000 0 28000 14000
32266.13633130 18219.22050526 24266.13633130 18219.22050526
3 50000 50000 69500 73000 99000 80000
impossible
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2016 K번