창 그리기

Andrew는 텍스트 모드 창 인터페이스를 사용하는 메일 프로그램을 새 운영체제로 이식하고 있다. 이 프로그램은 예전의 Norton 스타일 셸처럼 화면 버퍼에 문자를 써서 인터페이스를 그린다.

그런데 이 새 운영체제에서는 화면 버퍼에 접근하는 호출 하나하나가 매우 느리다. 문자 하나를 쓰는 데 $1/6000$초 이상이 걸리므로, 창을 문자 하나씩 다시 그리면 참을 수 없을 만큼 느리다.

속도를 높이기 위해 Andrew는 축에 나란한 직사각형 영역 전체를 한 번의 호출로 채우는 시스템 함수를 사용하려 한다. 그러면 창을 다시 그리는 일은 창의 보이는 영역을 가능한 한 적은 수의, 서로 겹치지 않는 직사각형으로 덮는 문제가 된다.

창의 보이는 부분이 직교 다각형(모든 변이 수평 또는 수직인 다각형)으로 주어진다. 이 영역을 정확히 덮는(합집합이 영역과 같고 서로 겹치지 않는) 축에 나란한 직사각형의 최소 개수를 구하여라.

보이는 영역은 그 경계로 주어지며, 경계는 정수 좌표를 갖는 수평 선분과 수직 선분으로만 이루어진다. 영역에는 구멍이 없고, 경계는 자기 자신과 닿거나 교차하지 않는다. 각 선분의 길이는 최소 1 이상이다.

첫째 줄에 경계의 꼭짓점 개수 $n$이 주어진다. 이어지는 $n$개의 줄에는 각 꼭짓점의 좌표가 반시계 방향으로 주어진다(화면에서 $y$축은 아래로 향한다). 수평 선분과 수직 선분이 번갈아 나타나며, 마지막 선분은 마지막 꼭짓점과 첫 꼭짓점을 잇는다.

$n \le 400$이고, 모든 좌표의 절댓값은 $200$ 이하이다.

보이는 영역을 서로 겹치지 않는 축에 나란한 직사각형들로 정확히 분할할 때 필요한 직사각형의 최소 개수 $m$을 정수 하나로 출력한다.