406336: GYM102365 F Fair Distribution

Memory Limit:1024 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Fair Distributiontime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

While wandering around the rural parts of Lalaland, Aram found himself in a backwards village so small that it wasn't named a number; instead, the village was named Lucca.

The $$$N$$$ villagers of Lucca faced a dilemma. The government of Lalaland decided to build a dam that would flood all of Lucca, and paid the town a lump sum to compensate for the land and relocation costs. Following Lalaland tradition, the lump sum was set to the area of the union of all polygons whose vertices are a subset of the villagers' homes, also known as the area of the convex hull of the villagers' homes. Unfortunately, there were no clear instructions on how to distribute the money.

Yrneh, who lived on the edge of village, demanded a larger share because his house alone increased the size of the lump sum. Leinad, who lived near Yrneh, complained that even if Yrneh wasn't there, his location ensured that the lump sum would be about the same. Accul, who lived near the center of the village, demanded at least some fraction of the lump sum, at least for relocation since his home would also be destroyed.

Aram, appalled by the uncivilized nature of the discussion in the backwards village, decided to step in and help before it came to blows. He devised a brilliant solution. He would consider the villagers in a random order, given by a permutation $$$p$$$. Then, for each $$$i$$$, he would calculate $$$A_i$$$, the traditional lump sum using only the homes of $$$p_1, p_2,\ldots p_i$$$. For increasing the sum, the villager $$$p_i$$$ would receive exactly their contribution $$$A_i-A_{i-1}$$$.

Yrneh complained that if he were unlucky enough to be considered first, he would get nothing. Aram thought for a bit and realized it would be more fair to take the expected value under this scheme, treating all $$$N!$$$ permutations as equally likely. He explained, using Lalaland's most sophisticated mathematics, that the total payout to the villagers would exactly equal the original lump sum.

This solution seems to have pleased everyone, so they turned to Aram to actually compute the amount of money each person would get. This is too much for Aram to compute by hand, so he needs your help!

Input

The first line contains $$$N$$$ ($$$1\le N \le 200$$$), the number of villagers.

Then follow $$$N$$$ lines, the $$$i$$$th of which contains two space separated integers $$$x_i$$$ and $$$y_i$$$ ($$$-10\,000 \le x_i, y_i \le 10\,000$$$), indicating the planar coordinates of a point representing villager $$$i$$$'s house. Homes are so small they can be treated as points. No two villagers have their homes at the exact same coordinates because all of them are single.

Output

Output $$$N$$$ lines. On line $$$i$$$, output the amount of money villager $$$i$$$ would get, as a floating-point number.

If the exact answer is $$$x$$$, your answer $$$y$$$ will be accepted if $$$\frac{|y-x|}{\max(x,\,1)} < 10^{-6}$$$.

ExampleInput
4
2 2
0 2
2 0
1 1
Output
0.8333333333333333
0.5
0.5
0.16666666666666666

加入题单

上一题 下一题 算法标签: