BOJ 1255 - 전쟁 - 선전포고 링크
(2023.05.12 기준 P4)

문제

N명의 백성과 직선 장애물 M개의 좌표가 주어지며, 백성은 속도도 같이 주어진다.
장애물을 통과할 수 없고, y=0인 국경을 향해 간다고 하였을 때, 모든 백성들이 국경을 넘는 최소 시간 출력

알고리즘

선분 교차 판정 및 다익스트라

풀이

BOJ 5449 - Farmer John 풀이와 거의 동일하다.
단, 목적지인 국경이 좀 말썽일 수 있다. 왜냐면, 모든 점에서의 가장 빠른 국경은 전부 다르기 때문. (7, 3)에서의 가장 빠른 국경은 (7, 0). (4, 6)에서의 가장 빠른 국경은 (4, 0)이 된다.

하지만 이는 국경으로의 거리를 계산할 때, 기준만 다르게 잡으면 되지. 모든 점마다의 국경을 선언할 필요는 없다.
어쨌든 모든 거리는 직선 거리이기 때문에, 경유를 하면 무조건 느려지게 되기 때문에 국경을 하나로 잡아도 무방하다.

그리고 이 문제는 좌표가 좀 특이하게 주어지는데, 알아서 잘 파싱하자.

코드

• C++

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> ppiii;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;

const int inf = INT_MAX;

double get_dist(pii a, pii b){
    return sqrt((a.f - b.f) * (a.f - b.f) + (a.s - b.s) * (a.s - b.s));
}

ll ccw(pii a, pii b, pii c){
    return (a.f * b.s + b.f * c.s + c.f * a.s) - (a.s * b.f + b.s * c.f + c.s * a.f);
}

bool is_intersect(pii a, pii b, pii c, pii d){
    ll ab = ccw(a, b, c) * ccw(a, b, d);
    ll cd = ccw(c, d, a) * ccw(c, d, b);
    // 일직선 상에서 포함하거나 겹치는 경우에도 선분이 교차하지 않는 것으로 판정
    return (ab < 0 && cd < 0);
}

pii parsing(string pos){
    int idx = pos.find(',');
    return {stoi(pos.substr(1, idx - 1)), stoi(pos.substr(idx + 1))};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<ppiii> people; // 백성
    for (int i = 0; i < N; i++){
        string pos; int v;
        cin >> pos >> v;
        people.push_back({parsing(pos), v});
    }

    vector<pii> points; // 장애물
    for (int i = 0; i < M; i++){
        string pos1, _, pos2;
        cin >> pos1 >> _ >> pos2;
        points.push_back(parsing(pos1));
        points.push_back(parsing(pos2));
    }

    M *= 2;
    int total = N + M * 2 + 1;
    vector<pid> graph[total];
    // 0 ~ N - 1 : 백성, N ~ N + M - 1 : 장애물, N + M: 국경(y=0)

    for (int i = 0; i < M; i++){
        // 장애물과 장애물의 거리
        for (int j = i + 1; j < M; j++){
            bool possible = true;
            for (int k = 0; k < M; k += 2)
                if (is_intersect(points[i], points[j], points[k], points[k + 1])){
                    possible = false;
                    break;
                }
            if (possible){
                double d = get_dist(points[i], points[j]);
                graph[i + N].push_back({j + N, d});
                graph[j + N].push_back({i + N, d});
            }
        }
        // 장애물과 국경의 거리
        pii border = {points[i].f, 0};
        bool possible = true;
        for (int j = 0; j < M; j += 2)
            if (is_intersect(points[i], border, points[j], points[j + 1])){
                possible = false;
                break;
            }
        if (possible){
            int d = points[i].s;
            graph[i + N].push_back({N + M, d});
            graph[N + M].push_back({i + N, d});
        }
    }

    double result = 0;
    for (int i = 0; i < N; i++){
        auto [person, v] = people[i];

        // 백성과 장애물의 거리
        for (int j = 0; j < M; j++){
            bool possible = true;
            for (int k = 0; k < M; k += 2)
                if (is_intersect(person, points[j], points[k], points[k + 1])){
                    possible = false;
                    break;
                }
            if (possible){
                double d = get_dist(person, points[j]);
                graph[i].push_back({j + N, d});
                graph[j + N].push_back({i, d});
            }
        }
        // 백성과 국경의 거리
        pii border = {person.f, 0};
        bool possible = true;
        for (int j = 0; j < M; j += 2)
            if (is_intersect(person, border, points[j], points[j + 1])){
                possible = false;
                break;
            }
        if (possible){
            int d = person.s;
            graph[i].push_back({N + M, d});
            graph[N + M].push_back({i, d});
        }

        // 다익스트라
        priority_queue<pdi, vector<pdi>, greater<pdi>> pq; pq.push({0, i});
        vector<double> distance(total, inf); distance[i] = 0;
        while (!pq.empty()){
            auto [d, here] = pq.top(); pq.pop();
            if (distance[here] < d) continue;
            for (auto [there, dd]: graph[here])
                if (distance[there] > d + dd)
                    distance[there] = d + dd, pq.push({distance[there], there});
        }

        // 시간 = 거리 / 속도
        result = max(result, distance[N + M] / v);
    }

    cout << fixed << setprecision(1) << result << '\n';
}

• Python

import sys; input = sys.stdin.readline
from math import floor, inf
from heapq import heappop, heappush

def get_dist(a, b):
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

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])

def is_intersect(a, b, c, d):
    ab = ccw(a, b, c) * ccw(a, b, d)
    cd = ccw(c, d, a) * ccw(c, d, b)
    # 일직선 상에서 포함하거나 겹치는 경우에도 선분이 교차하지 않는 것으로 판정
    return ab < 0 and cd < 0

N, M = map(int, input().split())

people = [] # 백성
for _ in range(N):
    pos, v = input().split(); v = int(v)
    x, y = pos.split(',')
    x = int(x[1:]); y = int(y[:-1])
    people.append(((x, y), v))

points = [] # 장애물
for _ in range(M):
    pos1, _, pos2 = input().split()
    x1, y1 = pos1.split(',')
    x1 = int(x1[1:]); y1 = int(y1[:-1])
    points.append((x1, y1))
    x2, y2 = pos2.split(',')
    x2 = int(x2[1:]); y2 = int(y2[:-1])
    points.append((x2, y2))

M *= 2
total = N + M  + 1
graph = [[] for _ in range(total)]
# 0 ~ N - 1 : 백성, N ~ N + M - 1 : 장애물, N + M : 국경(y=0)

for i in range(M):
    # 장애물과 장애물의 거리
    for j in range(i + 1, M):
        for k in range(0, M, 2):
            if is_intersect(points[i], points[j], points[k], points[k + 1]):
                break
        else:
            d = get_dist(points[i], points[j])
            graph[i + N].append((j + N, d))
            graph[j + N].append((i + N, d))

    # 장애물과 국경의 거리
    border = (points[i][0], 0)
    for j in range(0, M, 2):
        if is_intersect(points[i], border, points[j], points[j + 1]):
            break
    else:
        d = points[i][1]
        graph[i + N].append((N + M, d))
        graph[N + M].append((i + N, d))

result = 0
for i in range(N):
    person, v = people[i]

    # 백성과 장애물의 거리
    for j in range(M):
        for k in range(0, M, 2):
            if is_intersect(person, points[j], points[k], points[k + 1]):
                break
        else:
            d = get_dist(person, points[j])
            graph[i].append((j + N, d))
            graph[j + N].append((i, d))

    # 백성과 국경의 거리
    border = (person[0], 0)
    for j in range(0, M, 2):
        if is_intersect(person, border, points[j], points[j + 1]):
            break
    else:
        d = person[1]
        graph[i].append((N + M, d))
        graph[N + M].append((i, d))

    # 다익스트라
    queue = [(0, i)]
    distance = [inf] * total
    distance[i] = 0
    while queue:
        d, here = heappop(queue)
        if distance[here] < d:
            continue
        for there, dd in graph[here]:
            if distance[there] > d + dd:
                distance[there] = d + dd
                heappush(queue, (distance[there], there))

    # 시간 = 거리 / 속도
    result = max(result, distance[N + M] / v)

print(format(result, '.1f'))