「CC GEOCHEAT」-凸包

每次向平面中添加一个点 $P$,求当前点集的直径(任意两点最大距离)的平方。
数据随机

链接

CC GEOCHEAT

题解

考虑倒着删点,由于数据随机,我们可以先做一遍凸包和旋转卡壳得出答案及取得答案的两点,如果更早出现的点不在这两点上,那么答案就是当前得到的答案,否则直接重新做就好了。

期望复杂度 $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
/**
* Copyright (c) 2016-2018, xehoth
* All rights reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* 「CC GEOCHEAT」Bear and Shuffled Points 02-05-2018
* 凸包
* @author xehoth
*/
#include <bits/stdc++.h>
struct Point {
int x, y;
long long operator*(const Point &p) const {
return (long long)x * p.y - (long long)y * p.x;
}
Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
long long dis2(const Point &p) const {
return (long long)(x - p.x) * (x - p.x) +
(long long)(y - p.y) * (y - p.y);
}
bool operator<(const Point &p) const {
return x < p.x || (x == p.x && y < p.y);
}
};
const int MAXN = 750000;
int x[MAXN + 1], y[MAXN + 1];
std::tuple<Point, Point, long long> solve(int n) {
static std::vector<Point> p, c;
p.clear();
p.resize(n);
for (int i = 0; i < n; i++) {
p[i].x = x[i];
p[i].y = y[i];
}
if (n == 2) {
return std::make_tuple(p[0], p[1], p[0].dis2(p[1]));
}
std::sort(p.begin(), p.end());
c.clear();
c.resize(n * 2);
int top = 0, k;
for (int i = 0; i < n; i++) {
while (top > 1 && (c[top - 1] - c[top - 2]) * (p[i] - c[top - 2]) < 0)
top--;
c[top++] = p[i];
}
k = top;
for (int i = n - 2; i >= 0; i--) {
while (top > k && (c[top - 1] - c[top - 2]) * (p[i] - c[top - 2]) < 0)
top--;
c[top++] = p[i];
}
top--;
c.resize(top + 1);
c[top] = c[0];
Point ret1, ret2;
long long ret = 0;
for (int i = 0, j = 0; i < top; i++) {
while (c[i].dis2(c[j + 1]) >= c[i].dis2(c[j])) {
if (++j == top) j = 0;
}
long long d = c[i].dis2(c[j]);
if (d > ret) {
ret = d;
ret1 = c[i];
ret2 = c[j];
}
}
return std::make_tuple(ret1, ret2, ret);
}
long long ans[MAXN];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n;
std::cin >> n;
for (int i = 0; i < n; i++) std::cin >> x[i] >> y[i];
for (int k = n; k > 1;) {
Point p, q;
long long d;
std::tie(p, q, d) = solve(k);
ans[--k] = d;
while (k > 1 && (x[k] != p.x || y[k] != p.y) &&
(x[k] != q.x || y[k] != q.y))
ans[--k] = d;
}
for (int i = 0; i < n; i++) std::cout << ans[i] << ' ';
return 0;
}
分享到