====== Manhattan Mornings ======

===== 풀이 =====
  * [[ps:problems:boj:23035]]와 거의 동일한 문제.
  * [[ps:tutorial:격자 경로#방문할_때_1점을_얻는_점이_k개_있을_때|격자 경로에서 가장 많은 점수를 얻는 이동 경로]]를 찾는 문제로 링크에서 설명한대로 [[ps:tutorial:lis]]를 이용해서 O(klogk)에 풀 수 있다.
  * 다만 [[ps:problems:boj:23035]] 보다 더 귀찮아진 부분은, 시작점과 끝점의 위치관계에 따라서 LIS 또는 LDS를 사용해야 한다는 점.
    * 아래 코드에서는 LDS를 사용해야 하는 경우에는 그냥 y좌표에 모두 마이너스를 붙인 뒤에 LIS를 사용했다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 15015. Manhattan Mornings".

- Problem link: https://www.acmicpc.net/problem/15015
- Solution link: http://www.teferi.net/ps/problems/boj/15015

Tags: [LIS]
"""

import sys
from teflib import seqtask


def main():
    n = int(sys.stdin.readline())
    xh, yh, xw, yw = [int(x) for x in sys.stdin.readline().split()]
    x0, y0, x1, y1 = (xh, yh, xw, yw) if xh < xw else (xw, yw, xh, yh)
    if y0 > y1:
        y0, y1 = -y0, -y1
    coords = []
    for _ in range(n):
        x_i, y_i = [int(x) for x in sys.stdin.readline().split()]
        if y0 < 0:
            y_i = -y_i
        if x0 <= x_i <= x1 and y0 <= y_i <= y1:
            coords.append((x_i, y_i))

    seq = [y for x, y in sorted(coords)]
    answer = seqtask.longest_inc_subseq_length(seq, strict=False)

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:seqtask#longest_inc_subseq_length|teflib.seqtask.longest_inc_subseq_length]]

{{tag>BOJ ps:problems:boj:플래티넘_5}}