울타리
시간 제한1초메모리 제한1024 MB
최대 50,000개의 점이 주어질 때, 임의의 방향으로 놓인 직사각형이 모든 점을 포함하도록 하는 최소 둘레를 구한다.
문제
준석이는 목장 N채를 가지고 있다. 각 목장은 좌표평면 위의 점으로 나타낼 수 있다. 두 목장이 같은 위치에 있을 수 있다.
준석이는 모든 목장을 둘러싸는 직사각형 모양의 울타리를 치려고 한다. 직사각형의 변이 x축이나 y축에 꼭 평행할 필요는 없고, 변 위에 목장이 놓여 있어도 된다. 목장의 너비와 높이가 0이여도 된다.
모든 목장을 둘러싸는 울타리를 세웠을 때, 울타리의 최소 둘레를 구하여라.
입력
첫번째 줄에 목장의 수 N(2 ≤ N ≤ 50,000)이 주어진다.
다음 N줄에는 한 줄에 하나씩 목장의 x좌표와 y좌표가 주어진다. 모든 좌표는 절댓값이 2 × 10^8을 넘지 않는 정수이다.
출력
필요한 울타리의 최소 둘레를 출력한다. 절대/상대 오차는 10^−7까지 허용한다.