RiseOJ – 둘레

설명

농부 존(Farmer John)은 들판 한가운데에 N개 (1 <= N <= 50,000)의 건초 더미를 배치했다. 들판을 1 x 1 정사각형 칸들로 이루어진 1,000,000 x 1,000,000 격자로 생각하면, 각 건초 더미는 이 칸들 중 정확히 하나를 차지한다 (물론 어떤 두 건초 더미도 같은 칸을 차지하지 않는다).

FJ는 건초 더미들이 모두 하나의 큰 연결된 영역을 이룬다는 것을 알아챘다. 즉, 어느 더미에서 출발하든 바로 인접한 더미로 북, 남, 동, 서로 이동하는 단계들을 거쳐 다른 어떤 더미에도 도달할 수 있다. 다만 건초 더미들의 연결된 영역에는 "구멍", 즉 건초 더미로 완전히 둘러싸인 빈 영역이 있을 수 있다.

건초 더미들이 이루는 영역의 둘레를 구하는 것을 FJ에게 도와주자. 구멍은 둘레에 포함되지 않음에 유의하라.

제약

입력 형식

첫째 줄: 건초 더미의 수 N.

둘째 줄부터 1+N번째 줄까지: 각 줄에 건초 더미 하나의 (x,y) 위치가 주어지며, x와 y는 모두 1..1,000,000 범위의 정수이다. 위치 (1,1)은 왼쪽 아래 칸이고, 위치 (1000000,1000000)은 오른쪽 위 칸이다.

출력 형식

건초 더미들의 연결된 영역의 둘레.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 perimeter.in · 출력을 쓸 파일 perimeter.out

예제 1

입력

8
10005 200003
10005 200004
10008 200004
10005 200005
10006 200003
10007 200003
10007 200004
10006 200005

출력

설명

Output details: The perimeter of the connected region is 14; the hole in the middle does not contribute.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > February > Silver

올림피아드 > USACO > 2012-2013 > February > Silver

태그

JudgeUSACO

둘레

평가 및 의견

풀이 제출