볼록 격자 그래프 판별하기

점의 집합을 $S$라고 하자. 다음 세 조건이 모두 성립하는지 확인하면 된다.

• 같은 $x$좌표를 갖는 점들의 $y$좌표가 빈틈없이 연속한다.
• 같은 $y$좌표를 갖는 점들의 $x$좌표가 빈틈없이 연속한다.
• 그래프가 연결되어 있다.

먼저 이 조건들이 필요함을 보이자. 같은 $x$좌표를 갖는 두 점 $(x,a)$와 $(x,b)$를 생각하자. 두 점의 맨해튼 거리는 $|a-b|$이다. 길이가 정확히 $|a-b|$인 경로는 가로 방향 간선을 사용할 수 없다. 따라서 두 점 사이의 모든 격자점 $(x,y)$가 존재해야 한다. 같은 방법으로 같은 $y$좌표를 갖는 점들의 $x$좌표도 연속해야 한다. 모든 두 정점 사이의 거리가 유한해야 하므로 그래프는 연결되어 있어야 한다.

반대로 세 조건이 모두 성립한다고 하자. 두 정점 $u,v$ 사이의 최단 경로 하나를 고른다. 이 경로가 오른쪽과 왼쪽 방향 간선을 모두 사용한다고 가정하자. 그러면 경로 위에서 $x$좌표가 같은 두 정점을 끝점으로 하고, 내부에 가로 방향 간선을 포함하는 부분 경로를 고를 수 있다. 같은 $x$좌표 위의 점들은 연속하므로 두 끝점을 세로 방향으로 곧게 연결할 수 있다. 이 경로는 가로 방향 간선을 포함한 기존 부분 경로보다 짧으므로 최단 경로라는 가정에 모순이다. 따라서 최단 경로의 $x$좌표는 한 방향으로만 변한다. 같은 논리로 $y$좌표도 한 방향으로만 변한다. 그러므로 최단 경로의 길이는 정확히 맨해튼 거리이다.

구현에서는 점의 번호를 $(x,y)$ 순서로 정렬한다. 같은 $x$좌표를 갖는 인접한 두 점의 $y$좌표 차이가 항상 $1$인지 확인하고, 차이가 $1$이면 DSU로 합친다. 다음으로 $(y,x)$ 순서로 정렬하여 같은 검사를 반복한다. 빈틈이 하나라도 있으면 답은 NO이다. 모든 검사가 끝난 뒤 모든 점이 하나의 DSU 집합에 속하면 YES, 아니면 NO이다.

정렬이 두 번 필요하므로 시간 복잡도는 $O(N\log N)$이고, 메모리 복잡도는 $O(N)$이다.