#433 Recognizing Convex Grid Graphs

Loading problem...

Preparing the statement, recent submissions, and submit form.

DOJ/DOJ Contest/DOJ Contest 5

Authors: woohyunjng

Time limit: 3000 ms
Python time limit: 6000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

KO EN

서로 다른 $N$ 개의 격자점 $(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)$ 이 주어진다.

이 점들로 무향 그래프 $G$ 를 만든다. 각 점은 하나의 정점이다. 서로 다른 두 점 $(x_i,y_i)$ 와 $(x_j,y_j)$ 의 맨해튼 거리가 $1$ 이면 두 정점을 간선으로 연결한다.

두 점 $(x_i,y_i)$ 와 $(x_j,y_j)$ 의 맨해튼 거리는 다음과 같다.

|x_i-x_j|+|y_i-y_j|

그래프 $G$ 가 볼록 격자 그래프라는 것은, 임의의 두 정점 $i,j$ 에 대하여 그래프 $G$ 에서 두 정점 사이의 최단 거리와 두 점의 맨해튼 거리가 같다는 뜻이다. 두 정점이 연결되어 있지 않다면 두 정점 사이의 그래프상 거리는 무한대로 정의한다.

주어진 그래프가 볼록 격자 그래프인지 판별하여라.

Input

입력은 다음과 같은 형식으로 주어진다.

$N$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_N\ y_N$

Output

주어진 그래프가 볼록 격자 그래프라면 YES를, 아니라면 NO를 출력한다.

대문자와 소문자는 구분된다.

Constraints

$1 \leq N \leq 500\,000$ .
$-10^9 \leq x_i,y_i \leq 10^9$ ( $1 \leq i \leq N$ ).
$(x_i,y_i) \neq (x_j,y_j)$ ( $1 \leq i < j \leq N$ ).

Subtasks

#	Score	Constraints
1	24	$N \leq 100$ .
2	32	$N \leq 2\,000$ .
3	44	추가적인 제약이 없다.

Samples

Sample 1

Input

1
0 0

Output

YES

그래프에 정점이 하나뿐이므로 조건을 만족한다.

Sample 2

Input

Output

YES

임의의 두 점 사이를 두 점의 맨해튼 거리와 같은 개수의 간선으로 이동할 수 있다.

Sample 3

Input

2
0 0
1 1

Output

두 정점은 연결되어 있지 않다.

Sample 4

Input

Output

$(0,1)$ 과 $(2,1)$ 의 맨해튼 거리는 $2$ 이지만, 그래프상 최단 거리는 $4$ 이다.

Editorial

View editorial

볼록 격자 그래프 판별하기

Statement

Input

Output

Constraints

Subtasks

Samples

Editorial