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

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

새 차고지 짓기

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

요약
축에 나란한 직각 다각형의 꼭짓점 좌표가 순서 없이 주어질 때, 다각형을 복원해 전체 둘레의 길이를 구한다.
난이도

보통10점 중 5점

유형
기하, 정렬, 해시맵, 구현
정답자
아직 제출이 없습니다

문제

한 화물 운송 회사가 늘어나는 트럭 정비 수요에 맞추기 위해 새 차고지를 짓기로 했다. 차고지 부지는 담장으로 둘러싸이는데, 이 담장은 연결된 하나의 영역을 감싸며 담장의 각 구간은 남북 방향 또는 동서 방향으로만 놓인다. 담장의 방향이 바뀌는 지점마다 기둥이 하나씩 세워지고, 방향이 바뀌지 않는 곳에는 기둥이 없다(불필요한 기둥은 없다).

인부들이 모든 기둥을 세운 뒤 그만 설계도를 잃어버렸다. 모든 기둥의 좌표가 주어질 때, 담장의 전체 길이를 구하여라.

입력

입력은 여러 개의 블록으로 이루어진다. 각 블록의 첫 줄에는 세워진 기둥의 개수 PP (1≤P≤100 0001 \le P \le 100\,000)가 주어진다. 이어지는 PP개의 줄에는 각 기둥의 좌표를 나타내는 두 정수 XX, YY (0≤X,Y≤10 0000 \le X, Y \le 10\,000)가 주어진다. 어떤 두 기둥도 같은 좌표를 갖지 않는다.

각 블록 뒤에는 빈 줄이 하나 있으며, 입력의 끝은 00 하나만 있는 줄로 표시된다.

출력

각 블록마다 한 줄씩 출력한다. 각 줄은 정확히 The length of the fence will be L units. 형식이어야 하며, 여기서 L은 담장의 실제 길이로 바꾼다. 담장은 항상 만들 수 있다고 가정해도 된다.

예제3

  1. 예제 1

    입력
    6
    1 1
    1 3
    3 3
    2 1
    3 2
    2 2
    
    0
    
    예상 출력
    The length of the fence will be 8 units.
    
  2. 예제 2

    입력
    4
    0 0
    0 1
    1 1
    1 0
    
    0
    
    예상 출력
    The length of the fence will be 4 units.
    
  3. 예제 3

    입력
    4
    0 0
    0 5
    4 5
    4 0
    
    0
    
    예상 출력
    The length of the fence will be 18 units.