백준17625 고압선

작성일 | In

문제 링크

  • http://icpc.me/17625

문제 출처

  • 2019 KOI 고등부 4번

사용 알고리즘

  • Rotating Sweep Line

시간복잡도

  • $O(N^2 \log N)$

풀이

Subtask 1을 잘 생각해보면, 정답은 항상 아래 두 형태 중 하나라는 것을 알 수 있습니다.

  1. 두 점 $p_1, p_2$를 잇는 선분의 수직이등분선
  2. 세 점 $p_1, p_2, p_3$에 대해, $p_1$에서 선분 $p_2p_3$에 내린 수선의 수직이등분선

Subtask 3 ($N \leq 500$, 44점, $O(N^3)$)

이 문제를 $O(N^3)$에 해결하는 방법을 먼저 알아봅시다.

1번 케이스에 해당하는 직선 후보는 $O(N^2)$개 존재하고, 각 직선이 유효한지(두 점 $p_1, p_2$ 사이에 다른 점이 없는지) 확인하는데 $O(N)$이 걸리므로 총 $O(N^3)$에 처리할 수 있습니다.

2번 케이스는 약간 다른 방법으로 해결합니다.
$p_2, p_3$를 고정합시다. 이때 $p_1$이 될 수 있는 후보는 (1) 선분 $p_2p_3$의 왼쪽에 있는 점($ccw(p_2, p_3, p_1) = 1$) 중 선분과 가장 가까운 점, (2) 선분 $p_2p_3$의 오른쪽에 있는 점($ccw(p_2, p_3, p_1) = -1$) 중 선분과 가장 가까운 점, 두 가지로 축약할 수 있습니다.
그러므로 $p_2, p_3$를 고정하는 $O(N^2)$가지에 대해, 양쪽에서 가장 가까운 점을 $O(N)$만에 찾아주면 총 $O(N^3)$에 처리할 수 있습니다.

Subtask 5($N \leq 2000$, 100점, $O(N^2 \log N)$)

(1) 임의의 두 점 $p_1, p_2$ 사이에 다른 점이 없는지 판별하는 것, (2) 어떤 선분 $p_2p_3$과 가장 가까운 점을 찾는 것에 $O(N)$이라는 시간이 걸립니다. 이 시간을 줄일 수는 없을까요?

Rotating Sweep Line이라는 테크닉이 이 질문을 해결해줄 수 있습니다.

2번을 처리하는 방법을 먼저 알아봅시다.

선분 $p_2p_3$을 고정하고, 해당 선분과 수직인 직선에 모든 점을 사영시켜봅시다. 사영된 지점을 기준으로 번호를 붙여주면, 선분을 구성하는 두 점을 $i, j$번 점이라고 했을 때 왼쪽에서 가장 가까운 점은 $i-1$번 점이 되고, 오른쪽에서 가장 가까운 점은 $j+1$번 점이 됩니다.

비슷한 방식으로 1번도 처리할 수 있습니다.
선분 $p_1p_2$와 평행한 선분에 모든 점을 사영한 뒤, $p_1$과 $p_2$의 번호가 인접한지 확인하면 됩니다.

각 직선마다 점의 번호가 어떻게 바뀌는지 빠르게 구할 수 있다면 이 문제를 해결할 수 있습니다.
먼저, 주어지는 직선은 최대 $O(N^2)$가지입니다. 직선을 기울기 순서대로 보면, 각 직선마다 번호가 바뀌는 점은 최대 한 쌍만 존재하고, 그 두 점은 번호가 바뀌기 직전/직후에 인접한 상태를 유지합니다.
그러므로 직선을 기울기 순으로 $O(N^2 \log N)$에 정렬한 후, $O(N^2)$개의 직선은 순회하는 것으로 문제를 해결할 수 있습니다.

전체 코드

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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#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())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using Point = pair<ll, ll>;

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

ll _CCW(const Point &p1, const Point &p2, const Point &p3){ return (p2-p1)/(p3-p2); }
int CCW(Point p1, Point p2, Point p3){
    ll res = _CCW(p1, p2, p3);
    return (res > 0) - (res < 0);
}
ll D(const Point &p1, const Point &p2){
    ll dx = p1.x - p2.x, dy = p1.y - p2.y;
    return dx*dx + dy*dy;
}
inline double hypot(const Point p){ return hypot(p.x, p.y); }
inline Point Rot(const Point p){ return p.y >= 0 ? Point(p.y, -p.x) : Point(-p.y, p.x); }

int N, Idx[2020], Ord[2020];
Point A[2020];

struct Line{
    int i, j, flag; // -1: rot90
    Point s, e, dir;
    Line(int i, int j, int flag) : i(i), j(j), flag(flag), s(A[i]), e(A[j]) {
        if(s > e) swap(s, e);
        if(flag == 1) dir = e - s;
        else dir = Rot(e - s);
    }
    bool operator < (const Line &l) const {
        ll res = dir / l.dir; if(res) return res > 0;
        return tie(flag, s, e) < tie(l.flag, l.s, l.e);
    }
};

inline double solve_triangle(const Point &a, const Point &b, const Point &c){
    return abs(_CCW(a, b, c)) / hypot(a - b);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N; for(int i=1; i<=N; i++) cin >> A[i]; sort(A+1, A+N+1);
    for(int i=1; i<=N; i++) Ord[i] = Idx[i] = i;

    vector<Line> lines; lines.reserve(N*(N-1)/2);
    for(int i=1; i<=N; i++) for(int j=i+1; j<=N; j++) lines.emplace_back(i, j, 1), lines.emplace_back(i, j, -1);
    sort(all(lines));

    double mx = 0;
    for(const auto &line : lines){
        if(line.flag == 1){
            int a = line.i, b = line.j;
            swap(Idx[a], Idx[b]);
            swap(Ord[Idx[a]], Ord[Idx[b]]);
            a = Idx[line.i]; b = Idx[line.j]; if(a > b) swap(a, b);
            if(a-1 >= 1) mx = max(mx, solve_triangle(line.s, line.e, A[Ord[a-1]]));
            if(b+1 <= N) mx = max(mx, solve_triangle(line.s, line.e, A[Ord[b+1]]));
        }
        else{
            if(abs(Idx[line.i] - Idx[line.j]) == 1) mx = max(mx, hypot(A[line.i] - A[line.j]));
        }
    }
    cout << fixed << setprecision(10) << mx / 2 << "\n";
}