Problem D
Keep Him Inside

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:

  • The spell needs to be perfectly balanced: the sum of the fractions of power over all Sorcerers must equal $1$.

  • The centre of the spell should coincide with the prisoner. This means that the average of the positions of Sorcerers, weighted by the fraction of power they are channeling, should be the location of the prisoner.

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.

\includegraphics[width=0.9\textwidth ]{figure.pdf}
Figure 1: The prison of sample $1$. $S_1$, $S_2$, and $S_3$ are the Sorcerers, while $P$ is the prisoner. Note that $\frac13S_1 + \frac13 S_2+\frac13S_3 = \frac13(0,0)+\frac13(3,0)+\frac13(0,3)= (1,1) = P$.


  • The first line contains $3\leq n\leq 10$, the number of Sorcerers in guard towers and two integers $-10^4 \leq x, y\leq 10^4$, the coordinates of the prisoner.

  • Then follow $n$ lines, each of which contains two integers $-10^4 \leq x, y\leq 10^4$, the coordinates of a Sorcerer.

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.


  • Output $n$ lines where the $i$th line contains a real number between $0$ and $1$ inclusive: the fraction of power that the $i$th Sorcerer should use for the containment spell to work.

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.

Sample Input 1 Sample Output 1
3 1 1
0 0
3 0
0 3
Sample Input 2 Sample Output 2
4 2 1
0 0
4 0
4 4
0 4
Sample Input 3 Sample Output 3
5 4 3
0 2
0 -1
5 -2
5 4
2 5
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in