시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 179 | 91 | 50 | 49.020% |
상근이는 선영이의 채소를 훔친다. 선영이는 이를 막기위해 모든 채소를 울타리로 보호하려고 한다. 선영이는 최대한 값싸게(짧게) 울타리를 만들려고 한다. 알 수 없는 이유로 인해서 울타리는 직사각형 모양으로만 칠 수 있다.
모든 채소는 크기를 무시할 수 있으며, 이차원 평면 위의 점으로 나타낸다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채소의 수 N (3 ≤ N ≤ 10 000) 이 주어진다.다음 N개 줄에는 채소의 좌표를 나타내는 두 정수 Xi 와 Yi (0 ≤ Xi, Yi ≤ 10 000) 가 주어진다. 두 채소가 같은 좌표를 갖는 경우는 없다. 입력으로 주어지는 모든 채소가 한 직선 위에 있는 경우는 없다.
각 테스트 케이스마다 울타리의 둘레 t를 출력한다. 울타리의 변은 축에 평행하지 않아도 된다.
정답과의 차이는 0.0005까지 허용된다.
3 0 0 1 0 0 1 3 10 0 0 10 4 4 4 1 0 0 1 2 1 1 2
4 31.112698 5.656854
ICPC > Regionals > Europe > Central European Regional Contest > CTU Open Contest > CTU Open Contest 2013 O번