[Python] 4185번 Colliding Traffic

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

---

 

24/11/21

 

 

이전에 북마크 해두었던 문제 중 하나로, 약간의 케이스 분류를 동반한 수학적 방법으로 해결했다.

---

 

문제 접근 방식:

 

 

문제의 입력은 다음과 같다.

 

테스트 케이스가 $C$개 주어진다. 각 테스트 케이스 마다 보트의 개수인 $N$개와, 두 보트가 서로 $r$ 미터 안에 있으면 충돌한다고 판정하는 실수 $r$이 주어진다.

 

이후에는 $N$개의 보트에 대한 정보가 다음과 같이 주어진다.

$x, y, d, s$. 여기서 $x, y$는 보트의 초기 위치이고, $d$는 보트의 각도, $s$는 보트의 속력을 나타낸다.

 

$d=0$이라면 북쪽을, $d=90$이라면 동쪽을, 그런 식으로 시계 방향과 60분법으로 각도가 표현된다.

 

문제에서 요구하는 것은 각 테스트 케이스 마다, 임의의 두 보트가 서로 충돌하는 최소의 시간을 출력하는 것이다. 만약 모든 보트가 서로 충돌하지 않는다면 "No collision."을 출력하면 된다.

 

 

보트의 초기 위치와 보트의 각도, 보트의 속력이 주어지면 우리는 이 보트의 위치를 시간 $t$에 따른 형식으로 다음과 같이 표현할 수 있다.

 

$$\begin{cases} x = x_0 + \sin(d)s t \\ y = y_0 + \cos(d)s t \end{cases}$$

 

여기서 $x_0, y_0$는 보트의 초기 위치이다. 또한, $d$는 $y$축으로부터의 호도법으로 나타낸 각도이다. (문제에서 주어지는 각도는 육십분법으로 나타낸 각도이므로, radians함수를 통해 $d$를 바꿔야 한다.)

 

우리는 두 보트의 거리가 서로 $r$이하에 있다면 "충돌"했다고 판단한다.

 

두 보트의 위치를 위에서 나타낸 것처럼 시간 $t$에 따른 형식으로 표현할 수 있다. 편의 상 이 두 보트의 위치를 $x_1, y_1, x_2, y_2$라고 하자.

 

두 보트가 충돌한다면 다음과 같은 수식이 성립한다.

 

$$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \leq r \rightarrow (x_1 - x_2)^2 + (y_1 - y_2)^2 \leq r^2$$

 

오른쪽 수식을 조금 더 풀어서 써보자.

 

두 보트의 초기 위치를 각각 $x_{s1}, y_{s1}, x_{s2}, y_{s2}$라고 하고, 두 보트의 각도를 각각 $d_{1}, d_{2}$라고 하고, 두 보트의 속력을 각각 $s_1, s_2$라고 하자.

 

그러면 다음과 같이 표현할 수 있다.

 

$$\begin{align} (x_1 - x_2)^2 &= (x_{s1} - x_{s2} + (\sin(d_{1})s_{1} - \sin(d_{2})s_{2})t)^2 \\ (y_1 - y_2)^2 &= (y_{s1} - y_{s2} + (\cos(d_{1})s_{1} - \cos(d_{2})s_{2})t)^2 \end{align}$$

 

편의 상 $\sin(d_{1})s_{1} - \sin(d_{2})s_{2} = p_x$라고 하고, $x_{s1} - x_{s2} = q_x$라고 하자. 마찬가지로 $y$항도 해당되는 부분을 $p_y, q_y$라고 하자.

 

그러면 $(x_1 - x_2)^2 + (y_1 - y_2)^2$에 해당하는 부분을 다음과 같이 이차 식으로 적을 수 있다.

 

$$(p_{x}^2 + p_{y}^2)t^2 + 2(p_{x}q_{x} + p_{y}q_{y})t + (q_{x}^2 + q_{y}^2)$$

 

편의 상 2차 항, 1차 항, 상수를 각각 $a, b, c$로 표현하면 최종적으로 다음과 같이 표현할 수 있다.

 

$$at^2 + bt + c \leq r^2 \rightarrow at^2 + bt + c - r^2 \leq 0$$

 

이 조건을 만족한다면, 두 보트가 충돌한다고 이야기 할 수 있다.

 

 

먼저, $a, b, c$는 모두 임의의 숫자(정확히 말하면 $a$와 $c$는 모두 $0$보다 크거나 같다.)이기 때문에 이 식이 2차 식이라는 보장은 없다. 편의 상 $at^2 + bt + c - r^2 = f(t)$라고 표기하겠다.

 

따라서 다음과 같이 케이스 분류를 해야한다.

 

1. $a = 0$인 경우

1-1. $b = 0$인 경우

1-1-1. $c - r^2 > 0$인 경우.

이 경우에는 조건을 만족시키는 $t$가 존재하지 않는다. 즉, 두 보트가 만나는 시간을 INF로 반환하면 된다.

1-1-2. 그 외의 경우.

이 경우 $t$에 어떤 숫자를 넣더라도 항상 만족한다. 즉, 두 보트가 처음부터 만나므로, 만나는 최소 시간은 $0$이다.

1-2. $b \neq 0$인 경우($f(t)$가 일차 함수인 경우)

이 경우, 일차 함수의 근을 구한다.

1-2-1. 이 근이 $0$보다 작은 경우.

이미 처음부터 만나므로 $0$이다.

1-2-2. 그렇지 않은 경우.

그 근이 최소 시간이 된다. 반올림 하여 반환한다.

 

2. $a \neq 0$인 경우(이차 함수인 경우)

2-1. $f(t)$가 항상 $0$보다 큰 경우. 즉, 판별식이 $0$보다 작은 경우(허근을 가지는 경우)

이 경우, 항상 만나지 않으므로 INF를 반환한다.

2-2. 그 외의 경우

이 경우 $f(t)$의 두 실근을 구한다.

두 실근을 크기 순으로 root1, root2라고 할때,

2-2-1. 둘 다 음수인 경우.
조건을 만족하는 최소 시간은 없다.($t \geq 0$이므로) 따라서 INF를 반환한다.

2-2-2. root2만 양수인 경우.

이미 처음부터 만나는 상황이므로 $0$을 반환한다.

2-2-3. 둘다 양수인 경우.

root1을 반올림하여 반환한다.

 

이런 케이스 분류가 나오는 이유는 이차함수($a \geq 0$이라는 제약조건을 생각하자)와 일차함수($c \geq 0$이라는 제약조건을 생각하자)의 그림을 그려보면 쉽게 확인할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 4185번 Colliding Traffic
# 수학
'''
접근 방법:
깡 수
'''
import sys
input = sys.stdin.readline
from math import radians, sin, cos, inf, sqrt
from itertools import combinations

def collision_judge(boat1, boat2, r):
    x1, y1, d1, s1 = boat1
    x2, y2, d2, s2 = boat2
    px, qx = sin(radians(d1))*s1 - sin(radians(d2))*s2, x1-x2
    py, qy = cos(radians(d1))*s1 - cos(radians(d2))*s2, y1-y2
    a, b, c = px*px + py*py, 2*(px*qx + py*qy), qx*qx + qy*qy - r*r
    if a == 0:
        if b == 0:
            if c > 0:
                return inf
            else:
                return 0
        if -c/b < 0:
            return 0
        else:
            return round(-c/b)
    elif b*b - 4*a*c < 0:
        return inf
    else:
        root1, root2 = (-b-sqrt(b*b - 4*a*c))/(2*a), (-b+sqrt(b*b - 4*a*c))/(2*a)
        if root1 < 0 and root2 < 0:
            return inf
        elif root1 < 0 and root2 > 0:
            return 0
        else:
            return round(root1)
    
def solve():
    n, r = map(float, input().split()) # number of boats, collision distance
    n = int(n)
    boat_information = [tuple(map(float, input().split())) for _ in range(n)]
    min_time = inf
    for boat1, boat2 in combinations(boat_information, 2):
        time = collision_judge(boat1, boat2, r)
        if time < min_time:
            min_time = time
    if min_time == inf:
        return 'No collision.'
    return min_time

def main():
    C = int(input())  # number of testcases
    for _ in range(C):
        ans = solve()
        print(ans)
    return

main()