쓰러뜨리기
시간 제한1초메모리 제한64 MB
직사각형의 한 점을 고정하고 회전시킬 때 지나가면서 쓰러뜨리는 깃발 수가 가장 적은 고정점을 찾아 그 개수를 구합니다.
문제
John은 운전하는 법을 모르지만 운전면허 시험에는 계속 응시한다. 그는 지역 농장에 가는데, 그곳 땅 위에는 개의 깃발이 꽂혀 있다. 번째 깃발은 위치에 있다. John의 목표는 차를 몰면서 깃발을 최대한 적게 쓰러뜨리는 것이다.
John의 숙적인 감독관은 John이 깃발을 너무 많이 쓰러뜨려 혼란을 일으킬 것이라고 본다. 그래서 고대의 지팡이로 John 차의 한 점을 고정한다. 그러면 차는 그 점을 중심으로만 회전할 수 있다.
형식적으로 말하면, 깃발의 개수와 위치, 그리고 네 정수 , , , 가 주어진다. 이 네 수는 직사각형을 나타낸다. 는 왼쪽 위 꼭짓점이고, 는 너비, 는 높이다. 이 직사각형이 John의 차다. 직사각형 위의 한 점을 고정점으로 고르되, 직사각형이 그 점을 중심으로 회전하는 동안 쓰러지는 깃발이 최소가 되도록 한다. 회전 중 어느 순간이든 깃발이 직사각형 안이나 테두리 위에 놓이면 그 깃발은 쓰러진 것으로 본다. 모든 깃발은 처음에 차의 바깥에 엄격히 놓여 있다고 가정해도 된다.
입력
첫째 줄에 자연수 ()이 주어진다. 깃발의 개수다.
둘째 줄에 정수 , , , (, )가 주어진다. 와 는 짝수다.
다음 개의 줄에는 깃발의 위치 , ()가 한 줄에 하나씩 주어진다.
출력
한 줄에 를 출력한다. 는 고정점을 최적으로 골랐을 때 쓰러지는 깃발의 개수다.