백준19586 울타리

작성일 | In

문제 링크

  • http://icpc.me/19586

사용 알고리즘

  • 볼록껍질
  • 로테이팅 캘리퍼스

시간복잡도

  • $O(N \log N)$

풀이

임의의 2차원 점 집합의 Minimum Bounding Box는 그 점들의 Convex Hull의 Minimum Bounding Box와 같다는 사실은 쉽게 알 수 있습니다.
더 나아가, Convex Hull의 한 변과 겹치는(무수히 많은 교점이 존재하는) Minimum Bounding Box가 존재한다는 사실이 잘 알려져 있습니다.

Convex Hull을 구한 뒤, Convex Hull의 각 변에 대해 Bounding Box를 구하고, 그 중 최소 둘레를 구해봅시다.
반대쪽(180도) 변에 접하는 점은 Rotating Calipers를 이용해서 구할 수 있습니다. 이 방법을 응용하면, 오른쪽(90도), 왼쪽(270도) 변에 접하는 점도 Rotating Calipers를 이용해서 구할 수 있습니다.
벡터의 내적/외적을 잘 활용하면 됩니다.

전체 코드

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
/******************************
Author: jhnah917(Justice_Hui)
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Point;
istream& operator >> (istream &in, Point &t){
    in >> t.x >> t.y; return in;
}
Point operator + (const Point p1, const Point p2){
    return Point(p1.x+p2.x, p1.y+p2.y);
}
Point operator - (const Point p1, const Point p2){
    return Point(p1.x-p2.x, p1.y-p2.y);
}
ll operator * (const Point p1, const Point p2){ /// dot
    return p1.x*p2.x + p1.y*p2.y;
}
ll operator / (const Point p1, const Point p2){ /// cross
    return p1.x*p2.y - p2.x*p1.y;
}

int CCW(const Point &p1, const Point &p2, const Point &p3){
    ll res = (p2 - p1) / (p3 - p2);
    return (res > 0) - (res < 0);
}

ll D(const Point &p1, const Point &p2){
    return (p2-p1) * (p2-p1);
}

double D(const Point &p, const Point &q, const Point &dir){
    const Point r = p + dir;
    return 1.0 * abs((q-p)/(r-p)) / sqrt(D(p, r));
}

vector<Point> ConvexHull(vector<Point> &P){
    vector<Point> H;
    swap(P[0], *min_element(all(P)));
    sort(P.begin()+1, P.end(), [&P](const Point &a, const Point &b){
        int cw = CCW(P[0], a, b);
        if(cw) return cw > 0;
        return D(P[0], a) < D(P[0], b);
    });
    for(const auto &i : P){
        while(H.size() >= 2 && CCW(H[H.size()-2], H.back(), i) <= 0) H.pop_back();
        H.push_back(i);
    }
    return move(H);
}

void Solve(){
    int N; cin >> N;
    vector<Point> P(N);
    for(auto &i : P) cin >> i;
    vector<Point> H = ConvexHull(P);
    if(H.size() == 1){ cout << 0 << "\n"; return; }
    if(H.size() == 2){
        auto mn = *min_element(all(P));
        auto mx = *max_element(all(P));
        cout << fixed << setprecision(10) << 2.0*sqrt(D(mn, mx)) << "\n";
        return;
    }

    // Multiply by 4
    int M = H.size();
    for(int i=0; i<M; i++) H.push_back(H[i]);
    for(int i=0; i<M; i++) H.push_back(H[i]);
    for(int i=0; i<M; i++) H.push_back(H[i]);

    auto ChkU = [&H](int i, int j){
        return (H[i+1] - H[i]) / (H[j+1] - H[j]) > 0;
    };
    auto ChkL = [&H](int i, int j){
        return (H[i+1] - H[i]) / (H[j+1] - H[j]) > 0 || (H[i+1] - H[i]) * (H[j+1] - H[j]) < 0;
    };
    auto ChkR = [&H](int i, int j){
        return (H[i+1] - H[i]) / (H[j+1] - H[j]) > 0 && (H[i+1] - H[i]) * (H[j+1] - H[j]) > 0;
    };

    int u = 1, l = 1, r = 1;
    double mn = 1e18;
    for(int i=0; i<M; i++){
        if(u%M == i) u++; while(ChkU(i, u)) u++;
        if(l%M == i) l++; while(ChkL(i, l)) l++;
        if(r%M == i) r++; while(ChkR(i, r)) r++;

        Point v1 = H[i+1] - H[i];
        Point v2 = {v1.y, -v1.x};
        double now = D(H[i], H[u], v1) + D(H[l], H[r], v2);
        mn = min(mn, now*2);
    }
    cout << fixed << setprecision(10) << mn << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T = 1; while(T--) Solve();
}