[GYM101981D - 2018ICPC南京] Country Meow(三分 / 模拟退火)

89 阅读 0 评论 59 点赞

我是靠谱客的博主优秀水杯，这篇文章主要介绍[GYM101981D - 2018ICPC南京] Country Meow(三分 / 模拟退火)，现在分享给大家，希望可以做个参考。

传送门：Country Meow

题意为，在一个三维坐标系中，给定 n 个点，要求找到一个点，使得该点与这 n 个点中距离该点最远的点的距离最小，给出这个最小的距离值。

实际上，这个问题就相当于最小球覆盖问题。有三种做法：
① 最小球覆盖模板。计算几何模板，非常暴力。但我没有。
② 三分。求距离的函数是个单峰函数，可以通过三分查找来找到极值。但由于有 x、y、z 三个变量需要控制，所以采用三层嵌套的三分。
③ 模拟退火。随机化算法，在单峰的情况下，不断移动至极值。

三分

复制代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 2e2;
const double inf = 1e15;
const double eps = 1e-3;
struct Point
{
    double x, y, z;
    Point() {}
    Point(double x, double y, double z): x(x), y(y), z(z) {}
}p[maxn];
int n;
double ans;

void read()
{
    scanf("%d", &n);
    double x, y, z;
    for(int i = 0; i < n; ++i)
    {
        scanf("%lf%lf%lf", &x, &y, &z);
        p[i] = Point(x, y, z);
    }
}

double dis(Point u, Point v)
{
    double dx = u.x - v.x;
    double dy = u.y - v.y;
    double dz = u.z - v.z;
    return dx*dx + dy*dy + dz*dz;
}

double calDis(double x, double y, double z)
{
    double maxDis = 0;
    Point tp = Point(x, y, z);
    for(int i = 0; i < n; ++i)
        maxDis = max(maxDis, dis(tp, p[i]));
    return maxDis;
}

double threeDivideZ(double x, double y)
{
    double left = -1e6, right = 1e6;
    double lmid, rmid, val1, val2;
    double ret = inf;
    for(int i = 0; i  < 50; ++i)
    {
        lmid = left + (right-left)/3;
        rmid = right - (right-left)/3;
        val1 = calDis(x, y, lmid);
        val2 = calDis(x, y, rmid);
        ret = min(ret, min(val1, val2));
        if(val1 > val2)
            left = lmid;
        else
            right = rmid;
    }
    return ret;
}

double threeDivideY(double x)
{
    double left = -1e6, right = 1e6;
    double lmid, rmid, val1, val2;
    double ret = inf;
    for(int i = 0; i  < 50; ++i)
    {
        lmid = left + (right-left)/3;
        rmid = right - (right-left)/3;
        val1 = threeDivideZ(x, lmid);
        val2 = threeDivideZ(x, rmid);
        ret = min(ret, min(val1, val2));
        if(val1 > val2)
            left = lmid;
        else
            right = rmid;
    }
    return ret;
}

void solve()
{
    double left = -1e6, right = 1e6;
    double lmid, rmid, val1, val2;
    for(int i = 0; i  < 50; ++i)
    {
        lmid = left + (right-left)/3;
        rmid = right - (right-left)/3;
        val1 = threeDivideY(lmid);
        val2 = threeDivideY(rmid);
        if(val1 > val2)
            left = lmid;
        else
            right = rmid;
    }
    ans = min(val1, val2);
    printf("%.6fn", sqrt(ans));
}

int main()
{
    read();
    solve();
    return 0;
}

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
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 2e2;
const double inf = 1e15;
const double eps = 1e-3;
struct Point
{
    double x, y, z;
    Point() {}
    Point(double x, double y, double z): x(x), y(y), z(z) {}
}p[maxn];
int n;
double ans;

void read()
{
    scanf("%d", &n);
    double x, y, z;
    for(int i = 0; i < n; ++i)
    {
        scanf("%lf%lf%lf", &x, &y, &z);
        p[i] = Point(x, y, z);
    }
}

double dis(Point u, Point v)
{
    double dx = u.x - v.x;
    double dy = u.y - v.y;
    double dz = u.z - v.z;
    return dx*dx + dy*dy + dz*dz;
}

double calDis(double x, double y, double z)
{
    double maxDis = 0;
    Point tp = Point(x, y, z);
    for(int i = 0; i < n; ++i)
        maxDis = max(maxDis, dis(tp, p[i]));
    return maxDis;
}

double threeDivideZ(double x, double y)
{
    double left = -1e6, right = 1e6;
    double lmid, rmid, val1, val2;
    double ret = inf;
    for(int i = 0; i  < 50; ++i)
    {
        lmid = left + (right-left)/3;
        rmid = right - (right-left)/3;
        val1 = calDis(x, y, lmid);
        val2 = calDis(x, y, rmid);
        ret = min(ret, min(val1, val2));
        if(val1 > val2)
            left = lmid;
        else
            right = rmid;
    }
    return ret;
}

double threeDivideY(double x)
{
    double left = -1e6, right = 1e6;
    double lmid, rmid, val1, val2;
    double ret = inf;
    for(int i = 0; i  < 50; ++i)
    {
        lmid = left + (right-left)/3;
        rmid = right - (right-left)/3;
        val1 = threeDivideZ(x, lmid);
        val2 = threeDivideZ(x, rmid);
        ret = min(ret, min(val1, val2));
        if(val1 > val2)
            left = lmid;
        else
            right = rmid;
    }
    return ret;
}

void solve()
{
    double left = -1e6, right = 1e6;
    double lmid, rmid, val1, val2;
    for(int i = 0; i  < 50; ++i)
    {
        lmid = left + (right-left)/3;
        rmid = right - (right-left)/3;
        val1 = threeDivideY(lmid);
        val2 = threeDivideY(rmid);
        if(val1 > val2)
            left = lmid;
        else
            right = rmid;
    }
    ans = min(val1, val2);
    printf("%.6fn", sqrt(ans));
}

int main()
{
    read();
    solve();
    return 0;
}

模拟退火

复制代码

K
const double inf = 1e23;
const double eps = 1e-6;
const double T0 = 1e6;
struct Point
{
    double x, y, z;
    Point() {}
    Point(double x, double y, double z): x(x), y(y), z(z) {}
}p[maxn];
int n;

void read()
{
    scanf("%d", &n);
    double x, y, z;
    for(int i = 0; i < n; ++i)
    {
        scanf("%lf%lf%lf", &x, &y, &z);
        p[i] = Point(x, y, z);
    }
}

double dis(Point u, Point v)
{
    double dx = u.x - v.x;
    double dy = u.y - v.y;
    double dz = u.z - v.z;
    return dx*dx + dy*dy + dz*dz;
}

void solve()
{
    Point sp = Point(0, 0, 0);
    double T = T0, delta = 0.99;
    double ans = inf;

while(T > eps)
    {
        Point tp = p[0];
        for(int i = 1; i < n; ++i)
            if(dis(sp, tp) < dis(sp, p[i]))
                tp = p[i];
        ans = min(ans, dis(sp, tp));

sp.x += (tp.x - sp.x) / T0 * T;
        sp.y += (tp.y - sp.y) / T0 * T;
        sp.z += (tp.z - sp.z) / T0 * T;

T *= delta;
    }
    printf("%.9fn", sqrt(ans));
}

int main()
{
    read();
    solve();
    return 0;
}

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
K
const double inf = 1e23;
const double eps = 1e-6;
const double T0 = 1e6;
struct Point
{
    double x, y, z;
    Point() {}
    Point(double x, double y, double z): x(x), y(y), z(z) {}
}p[maxn];
int n;

void read()
{
    scanf("%d", &n);
    double x, y, z;
    for(int i = 0; i < n; ++i)
    {
        scanf("%lf%lf%lf", &x, &y, &z);
        p[i] = Point(x, y, z);
    }
}

double dis(Point u, Point v)
{
    double dx = u.x - v.x;
    double dy = u.y - v.y;
    double dz = u.z - v.z;
    return dx*dx + dy*dy + dz*dz;
}

void solve()
{
    Point sp = Point(0, 0, 0);
    double T = T0, delta = 0.99;
    double ans = inf;

    while(T > eps)
    {
        Point tp = p[0];
        for(int i = 1; i < n; ++i)
            if(dis(sp, tp) < dis(sp, p[i]))
                tp = p[i];
        ans = min(ans, dis(sp, tp));

        sp.x += (tp.x - sp.x) / T0 * T;
        sp.y += (tp.y - sp.y) / T0 * T;
        sp.z += (tp.z - sp.z) / T0 * T;

        T *= delta;
    }
    printf("%.9fn", sqrt(ans));
}

int main()
{
    read();
    solve();
    return 0;
}