색종이 자르기
시간 제한2초메모리 제한128 MB
다각형 모양의 색종이를 x축이나 y축에 평행한 직선으로 잘랐을 때 나오는 조각의 개수를 구합니다.
문제
평면 위에 다각형 모양의 색종이가 한 장 놓여 있다. 이 색종이를 x축 또는 y축에 평행한 하나의 직선으로 자르면, 색종이가 몇 조각으로 나뉘는지 구하라.
입력
첫째 줄에는 자르는 직선 위의 두 점 (x1, y1), (x2, y2)의 좌표가 주어진다. 이 직선은 x축 또는 y축에 평행하다.
둘째 줄에는 색종이를 나타내는 다각형의 꼭짓점 수 N이 주어진다. 다음 N개 줄에는 꼭짓점의 좌표 (x, y)가 한 줄에 하나씩 주어진다.
모든 좌표값은 공백으로 구분되며, 0 이상 1,000,000 이하의 정수이다. 꼭짓점은 반시계방향 순서로 주어지고, N은 3 이상 100,000 이하의 정수이다. 입력은 올바르게 주어지므로 별도의 오류 검사는 필요하지 않다. 자른 뒤 생기는 모든 다각형은 꼭짓점이 세 개 이상이다.
출력
첫째 줄에 색종이를 자른 뒤 생기는 조각 수를 출력한다.
힌트
추가 힌트는 없다.