Manhattan Mornings

• 가톨릭대는 고양이를 사랑해와 거의 동일한 문제.
• 격자 경로에서 가장 많은 점수를 얻는 이동 경로를 찾는 문제로 링크에서 설명한대로 가장 긴 증가하는 부분 수열 (LIS; Longest Increasing Subsequence)를 이용해서 O(klogk)에 풀 수 있다.
• 다만 가톨릭대는 고양이를 사랑해 보다 더 귀찮아진 부분은, 시작점과 끝점의 위치관계에 따라서 LIS 또는 LDS를 사용해야 한다는 점.
  • 아래 코드에서는 LDS를 사용해야 하는 경우에는 그냥 y좌표에 모두 마이너스를 붙인 뒤에 LIS를 사용했다.

"""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()

• Dependency: teflib.seqtask.longest_inc_subseq_length