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

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

볼록 껍질의 둘레를 가장 짧게 만들기

시간 제한2초메모리 제한512 MB

요약
n개의 점이 주어질 때, 두 점을 정확히 제거해서 얻을 수 있는 볼록 껍질 둘레의 최대 감소량을 구한다.
난이도

어려움10점 중 8점

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

문제

평면 위의 점이 세 개 이상 있고 모두 한 직선 위에 있지는 않을 때, 이 점 집합의 볼록 껍질은 집합의 모든 점을 경계나 내부에 포함하는 넓이가 가장 작은 볼록 다각형이다.

점 집합의 좌표가 주어진다. 집합에서 점을 두 개 빼면 볼록 껍질의 둘레가 얼마나 짧아지는지 구하라. 빼는 점은 정확히 두 개이며, 어느 두 점을 뺄지는 직접 고른다.

아래 그림은 예제 세 개에 해당한다. 동그라미로 표시한 점이 제외한 점이고, 굵은 점선이 가장 짧아진 볼록 껍질이다.

예제 1예제 2예제 3

입력

입력은 테스트 케이스 하나로 이루어지며 형식은 다음과 같다.

n
x1 y1
.
.
.
xn yn

nn은 집합에 속한 점의 개수이고 5≤n≤20005 \le n \le 2000이다. 각 ii마다 (xi,yi)(x_i, y_i)는 ii번째 점의 좌표이다. xix_i와 yiy_i는 −106-10^6 이상 10610^6 이하의 정수이다. 집합의 모든 점은 서로 다르다. 즉 j≠kj \ne k이면 xj≠xkx_j \ne x_k 또는 yj≠yky_j \ne y_k이다. 집합의 점을 n−2n - 2개 이상 지나는 직선은 없다.

출력

전체 집합의 볼록 껍질 둘레를 PP, 점을 두 개 뺀 집합의 볼록 껍질 둘레 중 가장 작은 값을 QQ라 하자. P−QP - Q를 소수점 아래 여섯 자리까지 출력한다.

예제3

  1. 예제 1

    입력
    10
-53 62
-19 58
-11 11
-9 -22
45 -7
37 -39
47 -58
-2 41
-37 10
13 42
    예상 출력
    72.963169

  2. 예제 2

    입력
    10
-53 62
-19 58
-11 11
-9 -22
45 -7
43 -47
47 -58
-2 41
-37 10
13 42
    예상 출력
    62.629480

  3. 예제 3

    입력
    10
-53 62
-35 47
-11 11
-9 -22
45 -7
43 -47
47 -58
-2 41
-37 10
13 42
    예상 출력
    61.581665