P3517 [POI2011] WYK-Plot
题目描述
We call any sequence of points in the plane a plot.
We intend to replace a given plot
The new plot is created as follows. The sequence of points
In that case we say that each of the points
As a result a new plot, represented by the points
The measure of such plot’s resemblance to the original is the maximum distance of all the points
An exemplary plot
For a given plot consisting of
Due to limited precision of floating point operations, a result is deemed correct if its resemblance to the given plot is larger than the optimum resemblance by at most
给定n个点,要求把n个点分成不多于m段,使得求出每段的最小覆盖圆的半径后,最大的半径最小。
输入格式
In the first line of the standard input there are two integers
Each of the following
The
输出格式
In the first line of the standard output one real number
In the second line of the standard output there should be another integer
Next, the following
Thus the
样例 #1
样例输入 #1
7 2
2 0
0 4
4 4
4 2
8 2
11 3
14 2
样例输出 #1
3.00000000
2
2.00000000 1.76393202
11.00000000 1.99998199
提示
给定n个点,要求把n个点分成不多于m段,使得求出每段的最小覆盖圆的半径后,最大的半径最小。
题目大意
1.题意:给一个有
解题思路
采取二分答案的思路,对圆半径进行二分答案,然后对于每个圆半径,我们可以采取随机增量法,随机增量法是一种求解最小圆覆盖的方法,其思路是随机选取一个点,然后遍历所有点,如果有点不在圆内,那么就更新圆心,然后再次遍历所有点,如果有点不在圆内,那么就更新圆心和半径,然后再次遍历所有点,如果有点不在圆内,那么就更新圆心和半径,这样就可以求出最小圆覆盖的圆心和半径。
不会随机增量法的先去做最小圆覆盖
check 函数用于判断是否可以将所有点分成不多于 m 个子集,使得求出每个子集的最小覆盖圆的半径后,最大的半径不超过 lim。
check 函数内部,同样使用二分答案,对于每个子集,使用随机增量法求出最小圆覆盖的圆心和半径,然后判断是否满足条件。
bool check(ld lim) {
cnt = 0;
int ans;
for (int i = 1; i <= n; i = ans + 1) {
int k;
for (k = 1; i + (1 << k) - 1 <= n; ++k) {
random_increment(i, i + (1 << k) - 1);
if (d > lim + eps) break;
}
ans = i;
int l = i + (1 << (k - 1)) - 1, r = min(n, i + (1 << k) - 1);
while (l <= r) {
int mid = (l + r) >> 1;
random_increment(i, mid);
if (d < lim + eps) l = mid + 1, ans = mid;
else r = mid - 1;
}
++cnt;
res[cnt][0] = i, res[cnt][1] = ans;
if (cnt > m) return false;
}
return true;
}
代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <random>
#include <iomanip>
using namespace std;
using ld = long double;
struct node {
ld x, y;
inline ld length() const {
return fabs(pow(x, 2) + pow(y, 2));
}
inline void transfer() {
x = -x;
swap(x, y);
}
node operator/(ld v) const { return node{x / v, y / v}; }
node operator*(ld v) const { return node{x * v, y * v}; }
friend node operator+(node &n1, node &n2) { return node{n1.x + n2.x, n1.y + n2.y}; }
friend node operator+(node &n1, node &&n2) { return node{n1.x + n2.x, n1.y + n2.y}; }
friend node operator-(node &n1, node &n2) { return node{n1.x - n2.x, n1.y - n2.y}; }
friend node operator*(node &n1, node &n2) { return node{n1.x * n2.x, n1.y * n2.y}; }
};
inline ld dis(node &p1, node &p2) {
return sqrt((p1 - p2).length());
}
inline ld cross(const node &p1, node &p2) {
return (p1.x * p2.y) - (p1.y * p2.x);
}
inline node get_circle(node &p1, node &p2) {
return (p1 + p2) / 2.0;
}
inline node get_circle(node &p1, node &p2, node &p3) {
node v1 = p2 - p1, v2 = p3 - p1;
v1.transfer(), v2.transfer();
node m1 = (p1 + p2) / 2.0, m2 = (p1 + p3) / 2.0;
ld t = cross(m2 - m1, v2) / cross(v1, v2);
return m1 + (v1 * t);
}
const ld eps = 1e-10;
const int N = 1e5 + 5;
int n, m, cnt;
int res[N][2];
node v[N], ps[N];
node o{};
ld d;
random_device rd;
mt19937 g(rd());
// 随机增量
inline void random_increment(int l, int r) {
copy(ps + l, ps + r + 1, v);
int len = r + 1 - l;
shuffle(v, v + len, g);
o = v[0], d = 0;
for (int i = 0; i < len; ++i) {
if (dis(o, v[i]) > d + eps) {
o = v[i], d = 0;
for (int j = 0; j < i; ++j) {
if (dis(o, v[j]) > d + eps) {
o = get_circle(v[i], v[j]);
d = dis(o, v[j]);
for (int k = 0; k < j; ++k) {
if (dis(o, v[k]) > d + eps) {
o = get_circle(v[i], v[j], v[k]);
d = dis(o, v[i]);
}
}
}
}
}
}
}
bool check(ld lim) {
cnt = 0;
int ans;
for (int i = 1; i <= n; i = ans + 1) {
int k;
for (k = 1; i + (1 << k) - 1 <= n; ++k) {
random_increment(i, i + (1 << k) - 1);
if (d > lim + eps) break;
}
ans = i;
int l = i + (1 << (k - 1)) - 1, r = min(n, i + (1 << k) - 1);
while (l <= r) {
int mid = (l + r) >> 1;
random_increment(i, mid);
if (d < lim + eps) l = mid + 1, ans = mid;
else r = mid - 1;
}
++cnt;
res[cnt][0] = i, res[cnt][1] = ans;
if (cnt > m) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> ps[i].x >> ps[i].y;
}
random_increment(1, n);
ld l = 0, r = d;
if (m > 1) {
while (r - l > eps) {
ld mid = (l + r) / 2.0;
if (check(mid)) r = mid;
else l = mid;
}
}
check(r);
cout << fixed << setprecision(8);
cout << r << '\n' << cnt << '\n';
for (int i = 1; i <= cnt; ++i) {
random_increment(res[i][0], res[i][1]);
cout << o.x << ' ' << o.y << '\n';
}
return 0;
}
复杂度分析
时间复杂度: