백준23197 Ley Lines

작성일 | In

문제 링크

  • http://icpc.me/23197

문제 출처

  • ICPC World Finals 2020 F번

사용 알고리즘

  • 불도저 트릭

시간복잡도

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

풀이

두 점이 연필의 한쪽 끝에 걸치는 경우만 고려해도 충분합니다. 즉, 두 점을 연결하는 직선을 잡은 뒤, 그 직선의 왼쪽에서 $t$ 만큼 떨어진 점의 개수와 오른쪽에서 $t$만큼 떨어진 점의 개수를 구하면 됩니다.
불도저 트릭을 하면서 파라메트릭 서치를 하면 $O(N^2 \log N)$에 해결할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
using Point = pair<ll, ll>;
constexpr long double EPS = 1e-9;

struct Line{
    ll i, j, dx, dy; // dx >= 0
    Line(int i, int j, const Point &pi, const Point &pj)
            : i(i), j(j), dx(pj.x-pi.x), dy(pj.y-pi.y) {}

    // dy / dx < l.dy / l.dx
    bool operator < (const Line &l) const {
        ll le = dy * l.dx, ri = l.dy * dx;
        return tie(le, i, j) < tie(ri, l.i, l.j);
    }
    bool operator == (const Line &l) const {
        return dy * l.dx == l.dy * dx;
    }
};

ll CCW(const Point &p1, const Point &p2, const Point &p3){
    return (p2.x - p1.x) * (p3.y - p2.y) - (p3.x - p2.x) * (p2.y - p1.y);
}

bool Check(const Point &p1, const Point &p2, const Point &p3, ll d){
    return abs(CCW(p1, p2, p3)) < d * hypotl(p2.x-p1.x, p2.y-p1.y) + EPS;
}

int N, K, Pos[3030], R;
Point A[3030];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> A[i].x >> A[i].y;
    sort(A+1, A+N+1); iota(Pos+1, Pos+N+1, 1);

    vector<Line> V; V.reserve(N*(N-1)/2);
    for(int i=1; i<=N; i++) for(int j=i+1; j<=N; j++) V.emplace_back(i, j, A[i], A[j]);
    sort(V.begin(), V.end());

    for(int i=0, j=0; i<V.size(); i=j){
        while(j < V.size() && V[i] == V[j]) j++;
        for(int k=i; k<j; k++){
            int u = V[k].i, v = V[k].j; // point id, index -> Pos[id]
            swap(Pos[u], Pos[v]); swap(A[Pos[u]], A[Pos[v]]);
            if(Pos[u] > Pos[v]) swap(u, v);

            int s = Pos[v], e = N;
            while(s < e){
                int m = (s + e + 1) / 2;
                if(Check(A[Pos[u]], A[Pos[v]], A[m], K)) s = m;
                else e = m - 1;
            }
            R = max(R, s - Pos[u] + 1);

            s = 1, e = Pos[u];
            while(s < e){
                int m = (s + e) / 2;
                if(Check(A[Pos[u]], A[Pos[v]], A[m], K)) e = m;
                else s = m + 1;
            }
            R = max(R, Pos[v] - e + 1);
        }
    }
    cout << R;
}