백준 20306 - 블랙홀

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

20306번: 블랙홀

[알고리즘 분류]

이분 탐색 + 스위핑

 

 

 일단 정해는 점과 직선의 거리를 이용하여 각 점이 블랙홀에 먹히는 시간을 구하는 것이다.

 나는 귀찮아서 그냥 파이썬을 이용해 이분 탐색으로 시간을 구했다.

 

 먼저 360도 정렬을 한다.

 블랙홀이 커질 때, 각 집이 어떤 선분에 제일 먼저 닿는지 구할 수 있다.

 이 선분이 언제 집을 집어삼키는지를 이분 탐색으로 찾으면 된다.

 

 정렬을 할 때, cmp_to_key를 사용하면 된다.

 
import sys
input = sys.stdin.readline
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
 
def mip(): return map(int, input().split())
def mfp(): return map(float, input().split())
def msp(): return map(str, input().split())
 
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
############ Main! #############
 
 
from functools import cmp_to_key
 
 
def cmp(x, y):
    if (x[0][0] <= 0) != (y[0][0] < 0):
        if x[0][0] > y[0][0]:
            return 1
        else:
            return -1
    else:
        if x[0][1] * y[0][0] < x[0][0] * y[0][1]:
            return -1
        return 1
 
def ccw(a,b,c):
    return a[0]*b[1]+b[0]*c[1]+c[0]*a[1] - a[1]*b[0]-b[1]*c[0]-c[1]*a[0] >= 0
 
 
def get(i,la,lb,ra,rb):
    lo = 0
    hi = 10 ** 19
 
    while lo <= hi:
        mid = (lo + hi) // 2
        l = [la, lb]
        r = [ra, rb]
        l[0] *= mid + 1
        l[1] *= mid + 1
        r[0] *= mid + 1
        r[1] *= mid + 1
        if ccw(l,r,v[i][0]):
            hi = mid - 1
        else:
            lo = mid + 1
    return lo
 
 
v = []
bl = []
cnt = []
n,m,k=mip()
px,py=mip()
for i in range(n):
    x,y=mip()
    v.append([[x-px,y-py],1])
    bl.append([[x-px,y-py],1])
for i in range(m):
    x,y=mip()
    v.append([[x-px,y-py],0])
 
v.sort(key=cmp_to_key(cmp))
bl.sort(key=cmp_to_key(cmp))
 
L = n - 1
for i in range(n+m):
    if v[i][1]:
        L = (L + 1) % n
        continue
    cnt.append(get(i, bl[L][0][0], bl[L][0][1], bl[(L+1)%n][0][0], bl[(L+1)%n][0][1]))
 
cnt.sort()
 
print(cnt[k-1])