백준 22942번 : 데이터 체커

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

22942번: 데이터 체커

 

스택 자료구조를 활용해서 푸는 문제이다.

 

x좌표상에 N개의 원이 존재하고, 각 원의 중심(x좌표)와 반지름이 주어진다. 이 N개의 원들 중에서 임의의 원 2개를 선택했을때 교점이 존재하는지 판단하는 문제이다. 즉, N개의 원 중 어느 것이라도 다른 원과 교점이 있으면 안된다.

 

데이터의 개수(N)이 최대 200,000이므로 N개 중에 2개를 선택하는 모든 경우의 수를 구하는 방법은 시간 초과 판정을 받기 때문에 다른 방법으로 문제를 해결해야 한다.

 

A (중심: a, 반지름: r1), B (중심: b, 반지름: r2)라는 두 원이 존재한다고 가정했을 때 다음 조건을 만족할 경우 두 원이 만난다(교점이 존재한다)고 얘기할 수 있다. (단, a - r1 <= b - r2)

• (a + r1) >= (b - r2)
• (a + r1) <= (b + r2)
• a - r1 = b - r2

다시말하면 두 원 A, B가 각각 x축과 만나는 점의 좌표를 보고 두 원 사이에 교점이 있는지 판단할 수 있다. 

 

존재하는 모든 원 마다 x축과 만나는 두 점(원의 시작점, 끝점)의 좌표를 튜플로 리스트에 저장하고, 원의 시작점을 기준으로 리스트를 정렬한다. 이렇게하면 x축에서 가장 먼저 그려지는 원의 시작점과 끝점이 리스트의 첫번째로 오게 된다.

 

이제 리스트를 순서대로 탐색하면서 각 튜플을 스택에 넣을 것이다. 그 전에 스택의 가장 위에 있는 튜플과 현재 탐색하는 튜플을 비교하여 위 조건에 따라 교점이 존재하는지 판단한다. 교점이 존재한다면 NO를 출력하고 프로그램을 종료하면 되고, 존재하지 않는다면 그 튜플을 스택에 넣는다.

 

만약 어떤 튜플을 스택에 넣으려고 할때 스택의 가장 위에 있는 튜플의 끝점보다 현재 넣으려고 하는 튜플의 시작점이 더 크다면, 스택을 pop해준다. 그 이유는 명확하게 교점이 존재하지 않는 두 원은 고려해줄 필요가 없기 때문이다. 

import sys
input = sys.stdin.readline

n = int(input())
S = []
for _ in range(n):
    x, r = map(int, input().split())
    S.append((x-r, x+r))
S.sort()
q = [S[0]]
for i in range(1, n):
    s, e = S[i]
    while q and s > q[-1][1]:
        q.pop()
    if not q:
        q.append(S[i])
        continue

    qs, qe = q[-1]
    if s == qs or e == qe or s == qe or (s < qe < e):
        print("NO")
        exit()
    q.append(S[i])
print("YES")