백준1255 전쟁 - 선전포고

작성일 | In

문제 링크

  • https://icpc.me/1255

사용 알고리즘

  • 선분 교차 판별
  • 다익스트라

풀이

이동할 때 선분의 중간 지점을 방문하지 않고 끝점만 방문하는 최단 경로가 존재함은 쉽게 알 수 있습니다.
선분의 양 끝점을 정점으로 하는 visibility graph를 만듭시다. $O(M^2)$개의 정점 쌍에 대해 간선을 만들 수 있는지 $O(M)$ 시간에 확인하면 총 $O(M^3)$ 시간에 그래프를 만들 수 있습니다.

visibility graph를 만들었다면 정답을 구하는 것은 간단합니다. 각 사람마다 한 번에 갈 수 있는 선분의 끝점들을 구한 다음, multi source dijkstra와 비슷한 방식으로 최단 거리를 구하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std; char _;
using Point = pair<int, int>;
istream& operator >> (istream &in, Point &pt){ return in >> _ >> pt.x >> _ >> pt.y >> _; }
double Dist(Point p1, Point p2){ return hypot(p2.x - p1.x, p2.y - p1.y); }
int CCW(Point p1, Point p2, Point p3){ return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y); }
int Intersect(Point a, Point b, Point c, Point d){ return CCW(a,b,c) * CCW(a,b,d) < 0 && CCW(c,d,a) * CCW(c,d,b) < 0; }

int N, M, V[55];
Point S[55], P[111];
vector<pair<int,double>> G[111];
void AddEdge(int u, int v, double w){ G[u].emplace_back(v, w); G[v].emplace_back(u, w); }

bool Check(int u, int v){
    for(int i=1; i<=M; i++) if(Intersect(P[u], P[v], P[i*2-1], P[i*2])) return false;
    return true;
}

double D[111], R;
double Solve(Point st){
    P[0] = {st.x, 0}; P[M+M+1] = st;
    if(Check(0, M+M+1)) return st.y;

    fill(D, D+111, 1e18);
    priority_queue<pair<double,int>, vector<pair<double,int>>, greater<>> Q;
    for(int i=1; i<=M+M; i++) if(Check(i, M+M+1)) Q.emplace(D[i]=Dist(st, P[i]), i);
    while(!Q.empty()){
        auto [c,v] = Q.top(); Q.pop();
        if(c == D[v]) for(auto [i,w] : G[v]) if(D[i] > c + w) Q.emplace(D[i]=c+w, i);
    }
    return D[0];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> S[i] >> V[i];
    for(int i=1; i<=M; i++) cin >> P[i*2-1] >> _ >> P[i*2];
    for(int i=1; i<=M+M; i++) for(int j=i+1; j<=M+M; j++) if(Check(i, j)) AddEdge(i, j, Dist(P[i], P[j]));
    for(int i=1; i<=M+M; i++) if(P[0] = {P[i].x, 0}, Check(0, i)) AddEdge(i, 0, P[i].y);

    for(int i=1; i<=N; i++) R = max(R, Solve(S[i]) / V[i]);
    cout << fixed << setprecision(1) << R;
}