아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Stop Making Sense

시간 제한1초메모리 제한256 MB

요약
각 점을 차례로 하나씩 제외하고 나머지 점을 모두 포함하는 가장 작은 볼록 다각형의 면적을 구합니다.
난이도

어려움10점 중 8점

유형
기하, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

2차원 평면에 점이 NN개 주어진다. 어느 세 점도 한 직선 위에 있지 않고, 따라서 좌표가 같은 점도 없다.

점을 하나씩 골라 그 점을 뺀다. 남은 N−1N-1개의 점을 모두 포함하는 볼록 다각형 가운데 넓이가 가장 작은 것을 생각하자. 각 점마다 이 최소 넓이를 구하라.

입력

첫째 줄에 정수 NN이 주어진다. (4≤N≤1000004 \le N \le 100000)

다음 NN개 줄에 점의 좌표 xix_i, yiy_i가 정수로 주어진다. (0≤xi,yi≤1090 \le x_i, y_i \le 10^9)

출력

NN개 줄을 출력한다. ii번째 줄에는 입력에서 ii번째로 주어진 점을 뺐을 때의 최소 넓이를 소수점 아래 셋째 자리까지, 세 자리를 모두 채워서 출력한다. 좌표가 모두 정수이므로 답은 항상 0.50.5의 배수다.

예제5

  1. 예제 1

    입력
    4
0 0
0 1
1 0
1 1
    예상 출력
    0.500
0.500
0.500
0.500

  2. 예제 2

    입력
    4
0 0
4 0
0 4
1 1
    예상 출력
    4.000
2.000
2.000
8.000

  3. 예제 3

    입력
    6
0 0
10 1
12 8
5 13
1 7
6 5
    예상 출력
    68.500
69.000
73.500
72.000
92.000
103.000

  4. 예제 4

    입력
    8
0 0
1000000000 0
1000000000 1000000000
0 1000000000
2 999999999
999999998 3
500000000 499999999
123456789 987654321
    예상 출력
    500000000500000000.000
999999997500000000.000
555555555327160495.500
999999998500000000.000
1000000000000000000.000
1000000000000000000.000
1000000000000000000.000
1000000000000000000.000

  5. 예제 5

    입력
    10
0 0
1 100
3 190
6 271
10 343
15 406
21 460
28 505
36 541
45 568
    예상 출력
    4536.000
6447.000
6448.000
6448.000
6448.000
6448.000
6448.000
6448.000
6448.000
4553.500