[python]伯準22942-データチェーン解答

Overview

BOJ 22942データチェーンPython回答
分類:データ構造(データ構造)

質問ページ

https://www.acmicpc.net/problem/22942

プールコード1

from sys import stdin


def main():
    def input():
        return stdin.readline().rstrip()

    n = int(input())
    circles = []
    for i in range(n):
        x, r = map(int, input().split())
        circles.append((x - r, i, 0))
        circles.append((x + r, i, 1))

    circles.sort()
    stack = []
    crds = set()
    for crd, i, flag in circles:
        if crd in crds:
            print("NO")
            return
        if flag == 0:
            stack.append((crd, i))
        elif stack[-1][1] != i:
            print("NO")
            return
        else:
            crds.add(crd)
            stack.pop()
    print("YES")


if __name__ == "__main__":
    main()

カッコマッチングの問題のように、スタックを使用して解きます.円とx軸の2つの頂点では,左が左かっこ,右が右かっこと考えられる.しかし,この問題では,円の接点が存在するか,一致する括弧が同じ円であるかを判断することはさらに困難である.

参考資料

https://velog.io/@dadahee/%EB%B0%B1%EC%A4%80-22942