ABC225E - フ

考え方

解説にあるように,偏角で考えれば「区間スケジューリング問題」に帰着する.
Editorial - UNICORN Programming Contest 2021(AtCoder Beginner Contest 225)

「区間スケジューリング問題」については,例えば蟻本を参照:
Pythonで蟻本2-2 - 貪欲法 - 競プロはじめました

ソートの方法が難しい.「偏角」や「傾き」を計算して,その値をもとにソートすると,誤差のため上手く行かない.

そこで,整数のまま比較できる「比較関数」をつくってソートする.

回答例

from functools import cmp_to_key

def f(r1, r2):
  x1, y1 = r1
  x2, y2 = r2
  return x2 * y1 - y2 * x1

def g(p1, p2):
  r1, s1 = p1
  r2, s2 = p2
  return f(r1, r2)

N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]
P = [((x - 1, y), (x, y - 1)) for x, y in P]
P.sort(key = cmp_to_key(g))

ans = 0
last = (1, -1)
for MAX, MIN in P:
  if f(MIN, last) >= 0:
    ans += 1
    last = MAX
print(ans)

【参考】【競プロ実況】ABC225 E問題【かつっぱ】 - YouTube