Informatica Online Judge

  운동장 점호 (Small) [1943 / 0797]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 2   Total Tried : 5


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (34th 백윤기)]
Writer ID : [gs16044]

Background

KOI 학교 사감 선생님들은 아침마다 학생들을 운동장에 세워놓고 같은 말을 반복하여 학생들을 고통스럽게 하는 것을 즐긴다.
이 때문에 많은 학생들이 운동장 점호에 늦거나 나오지 않으려고 한다.
사감 선생님들은 늦거나 참석하지 않은 학생들에게 벌을 주기 위해 울타리 안에 가두려 한다.

운동장은 x 좌표가 1 이상 1억 이하, y 좌표가 1 이상 1억 이하의 좌표평면이다.
사감 선생님들은 N 개의 점에다가 말뚝을 박았다.

그 후, 엄청나게 큰 고무밧줄을 구해 최대한 벌린 후, 놓았다.
고무밧줄은 탄성 때문에 말뚝에 걸릴때까지 줄어들었다.

고무 밧줄이 줄어들고 난 후, 그럴듯한 울타리가 만들어졌다.
하지만, 몇몇 말뚝은 밧줄이 걸쳐져 있지 않았고, 울타리 안에 있기도 했다.

학생들은 격자점에만 존재할 수 있으며, 말뚝이 박힌 곳에는 있을 수 없다.
사감선생님들은 모든 격자점에 학생을 배치했다.
이때, 울타리 내부(경계 포함)에 갇혀 벌을 받는 학생 수를 구하여라.

Input

첫 줄에 말뚝의 개수 N 이 입력된다. (500000 이하의 자연수)
다음 2~N+1 번째 줄에는 각 말뚝의 좌표 xi, yi 가 입력된다.
중복된 말뚝이 들어올 수 있다. 하지만 그 점에는 말뚝은 하나밖에 안 박힌 것이다.

제약 조건
Subtask #1 (20 점) : 울타리는 직사각형이다.
Subtask #2 (80 점) : 제약 조건 없음

Output

한 줄에, 울타리 내부(경계 포함)에 갇힌 학생 수를 구하여라.

IO Example

입력 예제 1
5
9 4
11 6
11 4
9 6
10 5

출력 예제 1
4

설명
울타리의 모양은 한 변의 길이가 2인 정사각형이다.
(10, 5)의 말뚝은 밧줄이 걸쳐져 있지 않고 울타리 내부에 있다.
따라서 학생들은 (9, 5), (11, 5), (10, 4), (10, 6) 의 4곳에만 있는다.


입력 예제 2
9
4 16
11 16
6 14
1 7
3 7
7 7
10 8
12 10
2 4

출력 예제 2
89

설명
(3, 7), (7, 7), (6, 14)는 밧줄이 걸쳐져 있지 않고 울타리 내부에 있다.
경계를 포함한 격자점은 총 98개인데 말뚝이 9개 이므로 89명의 학생이 들어간다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]