백준1830 거리

작성일 | In

문제 링크

  • http://icpc.me/1830

사용 알고리즘

  • 각종 기하 알고리즘

시간복잡도

  • $O(N \log N)$

풀이

맨해튼 거리를 45도 회전시키면 체비셰프 거리가 된다는 점을 활용하면 문제를 해결할 수 있습니다.

유클리드 거리에서 최대 거리는 Convex Hull을 구한 뒤 Rotating Calipers를 사용하면 $O(N \log N)$에 구할 수 있습니다.
유클리드 거리에서 최소 거리는 분할 정복이나 스위핑을 이용해 $O(N \log N)$에 구할 수 있습니다.
맨해튼 거리에서 최대 거리는 45도 회전시키면 체비셰프 거리에서의 최댓값을 구하는 문제가 되므로 $O(N)$에 구할 수 있습니다.
맨해튼 거리에서 최소 거리는 유클리드 거리에서 최소 거리를 구하는 것처럼 분할 정복을 이용해 $O(N \log N)$에 구할 수 있습니다.
체비셰프 거리에서 최대 거리는 x, y좌표의 최소/최대를 구하면 되므로 $O(N)$에 구할 수 있습니다.
체비셰프 거리에서 최소 거리는 45도 회전시키면 맨해튼 거리에서의 최솟값을 구하는 문제가 되므로 $O(N \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
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
176
/******************************
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>;
const Point O = {0, 0};
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

int CCW(const Point &p1, const Point &p2, const Point &p3){
    ll dx1 = p2.x - p1.x, dy1 = p2.y - p1.y;
    ll dx2 = p3.x - p2.x, dy2 = p3.y - p2.y;
    ll res = dx1 * dy2 - dx2 * dy1;
    return (res > 0) - (res < 0);
}
ll D1(const Point &p1, const Point &p2){
    return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}
ll D2(const Point &p1, const Point &p2){
    ll dx = p1.x - p2.x, dy = p1.y - p2.y;
    return dx * dx + dy * dy;
}

int N;
Point A[101010], T[101010];

vector<Point> ConvexHull(){
    vector<Point> v(A+1, A+N+1);
    vector<Point> ret;
    swap(v[0], *min_element(all(v)));
    sort(v.begin()+1, v.end(), [&](const Point &a, const Point &b){
        auto cw = CCW(v[0], a, b);
        if(cw) return cw > 0;
        return D2(v[0], a) < D2(v[0], b);
    });
    for(const auto &i : v){
        while(ret.size() >= 2 && CCW(ret[ret.size()-2], ret.back(), i) <= 0) ret.pop_back();
        ret.push_back(i);
    }
    return move(ret);
}
bool CalipersDirect(const Point &s1, const Point &e1, const Point &s2, const Point &e2){
    Point t1 = { e1.x - s1.x, e1.y - s1.y };
    Point t2 = { e2.x - s2.x, e2.y - s2.y };
    return CCW(O, t1, t2) >= 0;
}
pair<Point, Point> Calipers(){
    auto hull = ConvexHull();
    ll n = hull.size(), mx = 0; Point a, b;
    for(int i=0,j=0; i<n; i++){
        while(j+1 < n && CalipersDirect(hull[i], hull[i+1], hull[j], hull[j+1])){
            ll now = D2(hull[i], hull[j]);
            if(mx < now) mx = now, a = hull[i], b = hull[j];
            j++;
        }
        ll now = D2(hull[i], hull[j]);
        if(mx < now) mx = now, a = hull[i], b = hull[j];
    }
    return make_pair(a, b);
}

ll Solve1(int s=1, int e=N){
    if(s == e) return INF;
    int m = s + e >> 1;
    ll divLine = A[m].x, d = min(Solve1(s, m), Solve1(m+1, e));

    int l = s, r = m + 1, idx = s;
    while(l <= m && r <= e){
        if(A[l].y < A[r].y) T[idx++] = A[l++];
        else T[idx++] = A[r++];
    }
    while(l <= m) T[idx++] = A[l++];
    while(r <= e) T[idx++] = A[r++];
    for(int i=s; i<=e; i++) A[i] = T[i];

    vector<Point> now;
    for(int i=s; i<=e; i++){
        ll dx = abs(A[i].x - divLine);
        if(dx < d) now.push_back(A[i]);
    }

    ll ret = d;
    for(int i=1; i<now.size(); i++){
        for(int j=i-1; j>=0; j--){
            ll dy = abs(now[i].y - now[j].y);
            if(dy >= d) break;
            ret = min(ret, D1(now[i], now[j]));
        }
    }
    return ret;
}

ll Solve2(int s=1, int e=N){
    if(s == e) return INF;
    int m = s + e >> 1;
    ll divLine = A[m].x, d = min(Solve2(s, m), Solve2(m+1, e));

    int l = s, r = m + 1, idx = s;
    while(l <= m && r <= e){
        if(A[l].y < A[r].y) T[idx++] = A[l++];
        else T[idx++] = A[r++];
    }
    while(l <= m) T[idx++] = A[l++];
    while(r <= e) T[idx++] = A[r++];
    for(int i=s; i<=e; i++) A[i] = T[i];

    vector<Point> now;
    for(int i=s; i<=e; i++){
        ll dx = A[i].x - divLine;
        if(dx * dx < d) now.push_back(A[i]);
    }

    ll ret = d;
    for(int i=1; i<now.size(); i++){
        for(int j=i-1; j>=0; j--){
            ll dy = now[i].y - now[j].y;
            if(dy * dy >= d) break;
            ret = min(ret, D2(now[i], now[j]));
        }
    }
    return ret;
}

void Change(bool flag){
    for(int i=1; i<=N; i++){
        auto [x,y] = A[i];
        A[i] = {x + y, x - y};
        if(flag) A[i].x /= 2, A[i].y /= 2;
    }
}

ll MaxChebyshev(){
    ll X1 = INF, X2 = -INF, Y1 = INF, Y2 = -INF;
    for(int i=1; i<=N; i++){
        X1 = min(X1, A[i].x); X2 = max(X2, A[i].x);
        Y1 = min(Y1, A[i].y); Y2 = max(Y2, A[i].y);
    }
    return max(X2 - X1, Y2 - Y1);
}

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

    auto [p1,p2] = Calipers();
    cout << D2(p1, p2) << "\n";

    sort(A+1, A+N+1);
    cout << Solve2() << "\n";

    Change(false);
    cout << MaxChebyshev() << "\n";
    Change(true);

    sort(A+1, A+N+1);
    cout << Solve1() << "\n";

    cout << MaxChebyshev() << "\n";

    Change(false);
    sort(A+1, A+N+1);
    cout << Solve1() / 2 << "\n";
    Change(true);
}