백준 1255번: 전쟁 - 선전포고 [C++]

작성일 | In
플래티넘 4 플래티넘 4

문제

전쟁 - 선전포고

풀이

장애물의 끝 점을 정점으로 하는 그래프를 만들고 백성의 위치를 시작으로 하여 $y = 0$에 도달하는 최소 시간을 데이크스트라 알고리즘을 이용해 찾으면 됩니다.

구현의 편의를 위해, 그래프는 장애물의 끝 점만을 이용하여 만듭니다. 만약 두 점을 이은 직선과 교차하는 장애물이 없다면 간선을 이어줍니다.

이때, 장애물과 한 점에서 만나는 경우는 당연히 제외해야 합니다. 문제에서 직선 장애물이 서로 교차하지 않는다고 주어졌으므로 장애물의 양 끝 점과 고른 두 점중 점이 하나라도 같은 것이 존재하는지 확인하면 됩니다.

백성을 시작으로 $y = 0$에 도달하는 최소 시간 중 최댓값이 답이 됩니다.

정점의 개수는 최대 $2(N + 2M)$이고 간선의 개수는 최대 이것의 제곱이므로 시간 복잡도는 대략 $\mathcal{O}(4(N + 2M)^2\log 4(N + 2M)^2)$이 됩니다. 구현을 조금 비효율적으로 해도 $N$과 $M$이 매우 작으므로 통과할 수 있습니다.

코드

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif

using namespace std;

template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;

struct Point {
    int x, y;

    auto operator<=>(const Point& p) const = default;

    int crossProduct(const Point& p) const { return x * p.y - y * p.x; }

    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }

    long double dist(const Point& p) const {
        int dx = x - p.x;
        int dy = y - p.y;

        return sqrtl(dx * dx + dy * dy);
    }
};

int getCCW(const Point& p1, const Point& p2, const Point& p3) {
    int product = (p2 - p1).crossProduct(p3 - p1);

    if (product > 0)
        return 1;
    if (product < 0)
        return -1;
    return 0;
}

struct Line {
    Point s, e;

    Line() = default;
    Line(const Point& _s, const Point& _e) : s(_s), e(_e) {
        if (s > e)
            swap(s, e);
    }

    bool isIntersect(const Line& l) const {
        int ccw1 = getCCW(s, e, l.s) * getCCW(s, e, l.e);
        int ccw2 = getCCW(l.s, l.e, s) * getCCW(l.s, l.e, e);

        if (ccw1 == 0 and ccw2 == 0)
            return s <= l.e and l.s <= e;
        return ccw1 <= 0 and ccw2 <= 0;
    }
};

istream& operator>>(istream& in, Point& p) {
    string s;
    cin >> s;

    p.x = 0;
    int i = 1;
    while (s[i] != ',') {
        p.x *= 10;
        p.x += s[i++] - '0';
    }
    i++;

    p.y = 0;
    while (s[i] != ')') {
        p.y *= 10;
        p.y += s[i++] - '0';
    }

    return in;
}

vector<Point> points;
vector<vector<int>> adj;
vector<Line> obstacles;

bool canGoTo(const Point& s, const Point& e) {
    const Line l(s, e);

    for (const Line& obstacle : obstacles) {
        if (s == obstacle.s or s == obstacle.e or e == obstacle.s or e == obstacle.e)
            continue;

        if (l.isIntersect(obstacle))
            return false;
    }

    return true;
}

constexpr long double INF = 1e9;
long double getMinTime(const Point& citizen, int speed) {
    if (canGoTo(citizen, Point(citizen.x, 0)))
        return (long double)citizen.y / speed;

    vector<long double> time(points.size() + 1, INF);
    MinHeap<pair<long double, int>> pq;
    for (int i = 0; i < (int)points.size(); i++) {
        if (canGoTo(citizen, points[i])) {
            time[i] = citizen.dist(points[i]) / speed;
            pq.emplace(time[i], i);
        }
    }

    while (not pq.empty()) {
        auto [nowTime, now] = pq.top();
        pq.pop();

        if (time[now] < nowTime)
            continue;

        if (canGoTo(points[now], Point(points[now].x, 0)))
            time.back() = min(time.back(), nowTime + (long double)points[now].y / speed);

        for (int next : adj[now]) {
            long double nextTime = nowTime + points[now].dist(points[next]) / speed;

            if (nextTime < time[next]) {
                time[next] = nextTime;
                pq.emplace(nextTime, next);
            }
        }
    }

    return time.back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<pair<Point, int>> citizens(N);
    for (auto& [point, speed] : citizens) {
        cin >> point >> speed;
    }

    obstacles.resize(M);
    for (auto& [s, e] : obstacles) {
        cin >> s;
        cin.ignore(3);
        cin >> e;

        points.push_back(s);
        points.push_back(e);
    }

    adj.resize(points.size());
    for (int i = 0; i < (int)points.size(); i++) {
        for (int j = i + 1; j < (int)points.size(); j++) {
            if (canGoTo(points[i], points[j])) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    long double answer = 0;
    for (auto [citizen, speed] : citizens) {
        answer = max(answer, getMinTime(citizen, speed));
    }

    print("{:.1f}", answer);
    
    return 0;
}

백준 1255번: 전쟁 - 선전포고 [C++]