아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

쓰러뜨리기

시간 제한1초메모리 제한64 MB

요약
직사각형의 한 점을 고정하고 회전시킬 때 지나가면서 쓰러뜨리는 깃발 수가 가장 적은 고정점을 찾아 그 개수를 구합니다.
난이도

어려움10점 중 8점

유형
기하, 정렬, 투 포인터
정답자
아직 제출이 없습니다

문제

John은 운전하는 법을 모르지만 운전면허 시험에는 계속 응시한다. 그는 지역 농장에 가는데, 그곳 땅 위에는 NN개의 깃발이 꽂혀 있다. ii번째 깃발은 (xi,yi)(x_i, y_i) 위치에 있다. John의 목표는 차를 몰면서 깃발을 최대한 적게 쓰러뜨리는 것이다.

John의 숙적인 감독관은 John이 깃발을 너무 많이 쓰러뜨려 혼란을 일으킬 것이라고 본다. 그래서 고대의 지팡이로 John 차의 한 점을 고정한다. 그러면 차는 그 점을 중심으로만 회전할 수 있다.

형식적으로 말하면, 깃발의 개수와 위치, 그리고 네 정수 XX, YY, AA, BB가 주어진다. 이 네 수는 직사각형을 나타낸다. (X,Y)(X, Y)는 왼쪽 위 꼭짓점이고, AA는 너비, BB는 높이다. 이 직사각형이 John의 차다. 직사각형 위의 한 점을 고정점으로 고르되, 직사각형이 그 점을 중심으로 회전하는 동안 쓰러지는 깃발이 최소가 되도록 한다. 회전 중 어느 순간이든 깃발이 직사각형 안이나 테두리 위에 놓이면 그 깃발은 쓰러진 것으로 본다. 모든 깃발은 처음에 차의 바깥에 엄격히 놓여 있다고 가정해도 된다.

입력

첫째 줄에 자연수 NN (1≤N≤1051 \leq N \leq 10^5)이 주어진다. 깃발의 개수다.

둘째 줄에 정수 XX, YY, AA, BB (−107≤X,Y≤107-10^7 \leq X, Y \leq 10^7, 2≤A,B≤1072 \leq A, B \leq 10^7)가 주어진다. AA와 BB는 짝수다.

다음 NN개의 줄에는 깃발의 위치 xix_i, yiy_i (1≤xi,yi≤1071 \leq x_i, y_i \leq 10^7)가 한 줄에 하나씩 주어진다.

출력

한 줄에 KK를 출력한다. KK는 고정점을 최적으로 골랐을 때 쓰러지는 깃발의 개수다.

예제1

  1. 예제 1

    입력
    5
    -12 8 20 12
    9 1
    -9 -9
    3 12
    13 -4
    -5 13
    
    예상 출력
    2