백준25060 Pandemic Restrictions

작성일 | In

문제 링크

  • http://icpc.me/

문제 출처

  • 2021-2022 SWERC H번

사용 알고리즘

  • 삼분 탐색

시간복잡도

  • $O(\log^4 \epsilon)$

풀이

입력으로 주어진 세 점을 $a, b, c$, 새로 찍은 점을 $p$라고 합시다. $\triangle abp, \triangle bcp, \triangle cap$의 페르마 포인트의 비용의 최댓값을 최소화하는 $p$를 구해야 합니다.

일단 세 점이 주어졌을 때 페르마 포인트(세 점으로부터의 거리 합이 최소가 되는 점)을 구하는 방법을 알아봅시다. 거리 함수는 볼록 함수이므로 거리 함수들의 합도 볼록 함수입니다. 따라서 페르마 포인트는 삼분 탐색이나 경사 하강법 등으로 구할 수 있습니다. 정밀도 때문에 경사 하강법 보다는 삼분 탐색 2개를 중첩하는 것이 좋습니다. $O(\log^2 \epsilon)$에 구할 수 있습니다.

이제 실제 $p$의 위치를 구해야 하는데, $p$에 대한 비용도 볼록 함수이므로 $p$도 삼분 탐색으로 구할 수 있습니다. $p$를 찾는 것도 삼분 탐색 2개를 중첩해야 하므로 페르마 포인트를 $O(\log^2 \epsilon)$번 구해야 합니다. 전체 시간 복잡도는 $O(\log^4 \epsilon)$이고, $10^{-4}$ 정도의 정밀도만 요구하므로 생각보다 빠르게 돌아갑니다.

전체 코드

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
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ld = double;
using Point = pair<ld, ld>;
constexpr ld S = 10000, EPS = 1e-5;

Point operator + (const Point &p1, const Point &p2){ return {p1.x + p2.x, p1.y + p2.y}; }
Point operator - (const Point &p1, const Point &p2){ return {p1.x - p2.x, p1.y - p2.y}; }
ld Dist(const Point &p1, const Point &p2){ return hypot(p1.x - p2.x, p1.y - p2.y); }

bool Check(double a, double b){
    return abs(a - b) < max(EPS, max(abs(a), abs(b)) * EPS);
}

Point A, B, C;

ld FermatPoint(Point p1, Point p2, Point p3){
    auto cost = [&](Point p){
        return Dist(p1, p) + Dist(p2, p) + Dist(p3, p);
    };
    auto y_opt = [&](ld x){
        ld yl = min({p1.y, p2.y, p3.y});
        ld yr = max({p1.y, p2.y, p3.y});
        ld lo = cost(Point(x, yl));
        ld hi = cost(Point(x, yr));
        while(true){
            ld m1 = (yl + yl + yr) / 3;
            ld m2 = (yl + yr + yr) / 3;
            ld f1 = cost(Point(x, m1));
            ld f2 = cost(Point(x, m2));
            if(Check(f1, lo) && Check(f2, hi)) break;
            if(f1 < f2) yr = m2, hi = f2; else yl = m1, lo = f1;
        }
        return Point(x, (yl + yr) / 2);
    };
    ld xl = min({p1.x, p2.x, p3.x});
    ld xr = max({p1.x, p2.x, p3.x});
    ld lo = cost(y_opt(xl));
    ld hi = cost(y_opt(xr));
    while(true){
        ld m1 = (xl + xl + xr) / 3;
        ld m2 = (xl + xr + xr) / 3;
        ld f1 = cost(y_opt(m1));
        ld f2 = cost(y_opt(m2));
        if(Check(f1, lo) && Check(f2, hi)) break;
        if(f1 < f2) xr = m2, hi = f2; else xl = m1, lo = f1;
    }
    return cost(y_opt((xl + xr) / 2));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y;

    auto cost = [&](Point p){
        ld c1 = FermatPoint(A, B, p);
        ld c2 = FermatPoint(B, C, p);
        ld c3 = FermatPoint(C, A, p);
        return max({c1, c2, c3});
    };

    auto y_opt = [&](ld x){
        ld yl = min({A.y, B.y, C.y});
        ld yr = max({A.y, B.y, C.y});
        ld lo = cost(Point(x, yl));
        ld hi = cost(Point(x, yr));
        while(true){
            ld m1 = (yl + yl + yr) / 3;
            ld m2 = (yl + yr + yr) / 3;
            ld f1 = cost(Point(x, m1));
            ld f2 = cost(Point(x, m2));
            if(Check(f1, lo) && Check(f2, hi)) break;
            if(f1 < f2) yr = m2, hi = f2; else yl = m1, lo = f1;
        }
        return Point(x, (yl + yr) / 2);
    };

    ld xl = min({A.x, B.x, C.x});
    ld xr = max({A.x, B.x, C.x});
    ld lo = cost(y_opt(xl));
    ld hi = cost(y_opt(xr));
    while(true){
        ld m1 = (xl + xl + xr) / 3;
        ld m2 = (xl + xr + xr) / 3;
        ld f1 = cost(y_opt(m1));
        ld f2 = cost(y_opt(m2));
        if(Check(f1, lo) && Check(f2, hi)) break;
        if(f1 < f2) xr = m2, hi = f2; else xl = m1, lo = f1;
    }
    cout << fixed << setprecision(10) << cost(y_opt((xl + xr) / 2));
}