[BOJ 1177] 조쌤포스

문제

---

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

풀이

---

각 학생에 대해 빙정식 (t초가 지난 후의 조쌤과 학생의 거리 <= R)을 푼다.

해가 존재하면 그 구간들을 모아, 스위핑 기법을 이용해 제일 많은 겹친 구간들의 개수를 구한다.

식을 세우는 것보단 스위핑이 더 어려웠다.

실수할 여지도 많은 문제였다.

방정식이 0차부터 2차까지 모두 될 수 있으며, 해가 없을 수도 있다.

해 구간이 0을 중간에 포함한다면 시작점을 0으로 옮겨야 된다.

스위핑은 끝점들을 최소힙에 담아 구현했다.

코드

---

import sys
from heapq import heappush, heappop

n, r, x, y, dx, dy = map(int, sys.stdin.readline().split())
time = []
default = 0

for i in range(n):
    z, w, dz, dw = map(int, sys.stdin.readline().split())

    a = (dx - dz) ** 2 + (dy - dw) ** 2
    b = (x - z) * (dx - dz) + (y - w) * (dy - dw)
    c = (x - z) ** 2 + (y - w) ** 2 - r ** 2

    if a == 0:
        if b == 0:
            if c <= 0:
                default += 1
        elif (b > 0) and (c <= 0):
            time.append((0, - c / (2 * b)))
        
        continue
    
    D = b ** 2 - a * c

    if D >= 0:
        sol1 = (- b - D ** 0.5) / a
        sol2 = (- b + D ** 0.5) / a
        if sol2 >= 0:
            time.append((max(0, sol1), sol2))

time.sort()
end = []
ans = 0

for i in range(len(time)):
    p, q = time[i]
    heappush(end, q)

    while heap[0] < p:
        heappop(end)
    
    ans = max(ans, len(end))

print(default + ans)