시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 170 | 52 | 45 | 31.034% |
As a result of a long-standing war between the Sorcerers and the Orcs, you have been assigned as officer of one of the prison blocks. Recently the leader of the Orcs has been captured and placed inside a special cell. It works as follows: the cell is a convex polygon with at every vertex a guard tower in which a Sorcerer is placed.
Thanks to the recent agreement between the Sorcerers and Orcs, called the Beneficial Activities for Prisoners in Cells, the leader of the Orcs should be able to move around freely in his cell. You do not want your prisoner to escape, so you order the sorcerers to work together on a containment spell. If done right, this creates a magical aura around the prisoner that will prevent him from escaping.
In order for the containment spell to work, all Sorcerers need to channel a certain fraction of their maximum power into the spell such that two things hold:
Given the layout of the cell and the location of the prisoner, assign a fraction of power each Sorcerer should spend so that the containment spell works.
Figure K.1: The prison of sample 1. S1, S2, and S3 are the Sorcerers, while P is the prisoner. Note that (1/3)S1 + (1/3)S2 + (1/3)S3 = 1/3(0, 0) + 1/3(3, 0) + 1/3(0, 3) = (1, 1) = P.
It is guaranteed that the locations are given in counter clockwise order and form a strictly convex polygon, i.e. no three points lie on a line. The prisoner is located strictly inside the polygon.
If there are multiple possible solutions, you may output any one of them.
Your answer will be correct if the sum of fractions differs at most 10−4 from 1 and the weighted centre of your spell is within distance 10−4 of the prisoner. Note that it may not be sufficient to print your answer itself with 10−4 precision.
3 1 1 0 0 3 0 0 3
0.333333333333 0.333333333333 0.333333333333
4 2 1 0 0 4 0 4 4 0 4
0.5 0.25 0.25 0
5 4 3 0 2 0 -1 5 -2 5 4 2 5
0.2 0 0.1 0.7 0
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2019 K번