This page is still under construction.

Parts of this page are still being built. What you see may change.

Stop Making Sense

Time limit1sMemory limit256 MB

Summary
For each input point in turn, remove it and report the area of the smallest convex polygon enclosing the rest.
Level

Hard8 of 10

Topics
Geometry, Sorting, Binary search
Solved
No attempts yet

Problem

You are given NN points in the plane. No three of them lie on one line, so no two points share the same coordinates.

Take one point away at a time. Among all convex polygons that contain the remaining N−1N-1 points, consider the one of smallest area. Find that smallest area for every point.

Input

The first line contains an integer NN. (4≤N≤1000004 \le N \le 100000)

Each of the next NN lines contains the integer coordinates xix_i and yiy_i of one point. (0≤xi,yi≤1090 \le x_i, y_i \le 10^9)

Output

Print NN lines. On line ii, print the smallest area obtained when the ii-th point of the input is taken away, with exactly three digits after the decimal point. Every answer is a multiple of 0.50.5 because all coordinates are integers.

Examples5

  1. Example 1

    Input
    4
0 0
0 1
1 0
1 1
    Expected output
    0.500
0.500
0.500
0.500

  2. Example 2

    Input
    4
0 0
4 0
0 4
1 1
    Expected output
    4.000
2.000
2.000
8.000

  3. Example 3

    Input
    6
0 0
10 1
12 8
5 13
1 7
6 5
    Expected output
    68.500
69.000
73.500
72.000
92.000
103.000

  4. Example 4

    Input
    8
0 0
1000000000 0
1000000000 1000000000
0 1000000000
2 999999999
999999998 3
500000000 499999999
123456789 987654321
    Expected output
    500000000500000000.000
999999997500000000.000
555555555327160495.500
999999998500000000.000
1000000000000000000.000
1000000000000000000.000
1000000000000000000.000
1000000000000000000.000

  5. Example 5

    Input
    10
0 0
1 100
3 190
6 271
10 343
15 406
21 460
28 505
36 541
45 568
    Expected output
    4536.000
6447.000
6448.000
6448.000
6448.000
6448.000
6448.000
6448.000
6448.000
4553.500