[AHOI2012] 信号塔

发表于 | 分类于 >
字数统计 : 599   |   阅读时长 ≈ 3 mins.

题目

链接

[AHOI2012]信号塔

题意简述

求 个点的最小圆覆盖。

思路

一开始还傻傻的以为是平面最远点对。
一个等边三角形就可以 $hack$ 掉。

随机增量法

随机化！
随机加点，判断是否在圆内。
若不在。
若构成圆的点只有 $1$ 个点，则以它为圆心。
若构成圆的点有 $2$ 个点，则以它们的中点为圆心。
若构成圆的点有 $3$ 个点，则以它们的外心为圆心。
求外心别看别人的毒瘤公式，自己推一推就出来了。
也就是求两个一次函数的交点。
理论时间复杂度： $(n^{3})$ 。
期望时间复杂度： $(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
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e6 + 10, kmax_int = 2147483647, kmod = 1e4;
const double eps = 1e-6;

#define pdd std::pair<double, double>
#define mp std::make_pair
#define x first
#define y second
#define sqr(x)  ((x) * (x))

int n;
pdd point[kmax_num];
double r;

inline double Dist(REG int a, REG int b)  {
    return (double) sqrt(sqr(point[a].x - point[b].x) + 
                         sqr(point[a].y - point[b].y));
}

inline bool In(REG int a)   {
    return Dist(n, a) - r < eps;
}

inline void Get(REG int a, REG int b, REG int c) {
    REG double  k1 = -1 / ((point[a].y - point[b].y) / (point[a].x - point[b].x)),
                k2 = -1 / ((point[b].y - point[c].y) / (point[b].x - point[c].x));
    REG double  b1 = (point[a].y + point[b].y) / 2 - k1 * (point[a].x + point[b].x) / 2,
                b2 = (point[b].y + point[c].y) / 2 - k2 * (point[b].x + point[c].x) / 2;
    REG double  bx = - (b1 - b2) / (k1 - k2);
    point[n] = mp(bx, k1 * bx + b1);
    return ;
}

int main()  {
    scanf(" %d", &n);
    REG double ax, ay;
    FOR(i,0,n)  {
        scanf(" %lf %lf", &ax, &ay);
        point[i] = mp(ax, ay);
    }
    std::random_shuffle(point, point + n);
    
    point[n] = point[0];
    FOR(i,0,n)  if(!In(i)){
        point[n] = point[i];
        r = 0.000;

        FOR(h,0,i) if(!In(h)){
            point[n].x = (point[i].x + point[h].x) / 2;
            point[n].y = (point[i].y + point[h].y) / 2;
            r = Dist(n, i);

            FOR(k,0,h) if(!In(k)){
                Get(i, h, k);
                r = Dist(n, i);
            }
        }
    }
    printf("%.2lf %.2lf %.2lf\n", point[n].x, point[n].y, r);
    return 0;
}

杂项

  • 推外心公式时还忘了变号，调了调了一晚上。
  • 这里还是用了 $std::pair$ ，$std::pair$ 大法好！