백준(BAEKJOON) 22942 데이터 체커 - Python

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

22942번: 데이터 체커

 

 

과정

 

중심 좌표는 x축 기준

교점이 존재해서는 안됨 → 원 두개 잇을때 이중원? 아니면 아예 별도로

개수n

중심좌표 x

반지름 r

원 시작좌표 끝좌표

x-r = 시작좌표 x+r 끝좌표

 

 

풀이

import sys
input = sys.stdin.readline
# 원의 개수 입력
N = int(input())

# 각 원의 정보 입력 및 처리
circles_point = []
# 원들이 서로 겹치는지 확인
stack = []
for i in range(N):
    x, r = map(int, input().split())
    circles_point.append((x - r, i, 0))  # 원의 시작점
    circles_point.append((x + r, i, 1))  # 원의 끝점

# x좌표를 기준으로 정렬
circles_point.sort()

for point in circles_point:
    x, close, open = point
    if open == 0:  # 원 시작지점
        stack.append(point)
    else:  # 원 끝지점
        if stack[-1][1] != close:  # 스택의 마지막 원과 번호가 다르면 겹치는 것
            print("NO")
            exit(0)
        stack.pop()  # 스택에서 제거
print("YES")  # 모든 원이 겹치지 않음