난이도

Platinum 5

인증

문제

To repel the invading thirsty aardvarks, Farmer John wants to build a moat around his farm. He owns N (8 <= N <= 5,000) watering holes, and will be digging the moat in a straight line between pairs of them. His moat should protect (i.e., surround) all his watering holes; every watering hole must be on or inside the moat, and the moat must form a closed loop.

Digging a moat is expensive work, and frugal FJ wants his moat to have the minimum length possible. Find the length of the shortest moat he can construct.

The unique holes are each located at integer coordinates in the range (1..45,000, 1..45,000). FJ has noticed that no three watering holes lie along the same line.

Consider this grid where the 20 ‘*’s represent watering holes:

...*-----------------*......
../..........*........\.....
./.....................\....
*......................*\...
|..........*........*....\..
|*........................\.
|..........................*
*..........................|
.\*........................|
..\.....................*..|
...\........*............*.|
....\..................*...*
.....\..*..........*....../.
......\................../..
.......*----------------*...

The enclosing lines are the shortest possible path that can enclose this set of watering holes.

The line displacements, starting with the top line are: (18,0), (6,-6), (0,-5), (-3,-3), (-17,0), (-7,7), (0,4), and (3,3). This yields a distance of 70.8700576850888(…). Our output will print only two decimal places, so the distance will be reported as 70.87.

입력

Line 1: A single integer, N Lines 2..N+1: Two space-separated integers, X_i and Y_i that specify the location of a watering hole.

출력

Line 1: A single number D, the shortest possible length of moat. Print this number to two decimal places.

예제 입력

20
2 10
3 7
22 15
12 11
20 3
28 9
1 12
9 3
14 14
25 6
8 1
25 1
28 4
24 12
4 15
13 5
26 5
21 11
24 4
1 8

예제 출력

70.87

해설 및 후기

이 문제는 약간 Cows의 열화판이라고 할 수 있는 문제이다. 우선 볼록 껍질을 올바르게 구한 뒤, 그것이 이루는 선의 길이를 구한다. 두 점 사이의 거리를 구하는 공식을 사용해 이를 어렵지 않게 풀이할 수 있었다. 그러나 이 문제의 출력에 항상 소수점 2자리가 들어가야 한다는 것을 몰랐어서 엄청나게 많이 틀렸다.

제출 코드

import sys
import math
n = int(sys.stdin.readline().rstrip())

def ccw(a,b,c):
    res = (b[0]-a[0])*(c[1]-a[1]) - (c[0]-a[0])*(b[1]-a[1])
    if(res < 0):
        return -1
    elif(res > 0):
        return 1
    else:
        return 0

lsts = []
for i in range(n):
    x,y = sys.stdin.readline().rstrip().split()
    lsts.append([int(x),int(y)])

lsts = sorted(lsts, key=lambda x:(x[0], x[1]))
stk = []
for point in lsts:
    while(len(stk)>1 and ccw(stk[-2], stk[-1], point)<=0):
          stk.pop()
    stk.append(point)
tmpStk = stk[:]
stk = []
for point in lsts:
    while(len(stk)>1 and ccw(stk[-2], stk[-1], point)>=0):
          stk.pop()
    stk.append(point)
def getLen(a,b):
    return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5

res = 0
for i in range(len(tmpStk)-1):
    res += getLen(tmpStk[i],tmpStk[i+1])
for i in range(len(stk)-1):
    res += getLen(stk[i],stk[i+1])

print("{:.2f}".format(res))