Chaos Slover 补档计划 - 随机增量法

2015.11.18 20:29 Wed| 8 visits oi_2016| ChaosSlover补档计划| Text

BZOJ1336&1337 [Balkan2002]Alien最小圆覆盖

随机增量法就是对 O(N^3) 的暴力计算期望,强行让期望时间复杂度变成 O(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
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define eps 0.00000001
#define sqr(x) ((x) * (x))

int n;
double r;
pair<double, double> p[N], o;

double dist(pair<double, double> x, pair<double, double> y)
{
    return sqr(x.first - y.first) + sqr(x.second - y.second);
}

pair<double, double> calc(double a1, double b1, double c1,
                          double a2, double b2, double c2)
{
    return make_pair(((c1 * b2) - (c2 * b1)) / ((a1 * b2) - (a2 * b1)),
                     ((a1 * c2) - (a2 * c1)) / ((a1 * b2) - (a2 * b1)));
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", &p[i].first, &p[i].second);
    random_shuffle(p + 1, p + n + 1);
    o = p[1]; r = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (dist(p[i], o) < r + eps) continue;
        o = p[i], r = 0;
        for (int j = 1; j < i; ++j)
        {
            if (dist(p[j], o) < r + eps) continue;
            o = make_pair((p[i].first + p[j].first) / 2,
                          (p[i].second + p[j].second) / 2);
            r = dist(o, p[i]);
            for (int k = 1; k < j; ++k)
            {
                if (dist(p[k], o) < r + eps) continue;
                o = calc(2 * (p[j].first - p[i].first),
                         2 * (p[j].second - p[i].second),
                         sqr(p[j].first) + sqr(p[j].second)
                            - sqr(p[i].first) - sqr(p[i].second),
                         2 * (p[k].first - p[i].first),
                         2 * (p[k].second - p[i].second),
                         sqr(p[k].first) + sqr(p[k].second)
                             - sqr(p[i].first) - sqr(p[i].second));
                r = dist(o, p[i]);
            }
        }
    }
    cout << fixed << setprecision(10) << sqrt(r) << '\n'
            << o.first << ' ' << o.second << endl;
    return 0;
}

BZOJ3564 [SHOI2014]信号增幅仪

坐标变换之后拿最小圆覆盖做。由于询问的是半长轴长度,那么就顺时针把点都绕原点旋转 a 度之后横坐标除以 p 就好了。// 最开始推了半天什么鬼的变换公式 T^T

坐标旋转公式(逆时针):

另外对于这道题 pi 一定要足够精确。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 50005
#define eps 1e-10
#define sqr(x) ((x) * (x))

int n;
double r, sina, cosa, a, q;
pair<double, double> p[N], o;

double dist(pair<double, double> x, pair<double, double> y)
{
    return sqr(x.first - y.first) + sqr(x.second - y.second);
}

pair<double, double> calc(double a1, double b1, double c1,
                          double a2, double b2, double c2)
{
    return make_pair(((c1 * b2) - (c2 * b1)) / ((a1 * b2) - (a2 * b1)),
                     ((a1 * c2) - (a2 * c1)) / ((a1 * b2) - (a2 * b1)));
}

pair<double, double> change(pair<double, double> p)
{
    return make_pair(p.first * cosa - p.second * sina,
                     p.first * sina + p.second * cosa);
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> p[i].first >> p[i].second;
    cin >> a >> q;
    a = -a / 180 * acos(-1);
    sina = sin(a); cosa = cos(a);
    for (int i = 1; i <= n; ++i)
        p[i] = change(p[i]), p[i].first /= q;
    random_shuffle(p + 1, p + n + 1);
    o = p[1]; r = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (dist(p[i], o) < r + eps) continue;
        o = p[i], r = 0;
        for (int j = 1; j < i; ++j)
        {
            if (dist(p[j], o) < r + eps) continue;
            o = make_pair((p[i].first + p[j].first) / 2,
                          (p[i].second + p[j].second) / 2);
            r = dist(o, p[i]);
            for (int k = 1; k < j; ++k)
            {
                if (dist(p[k], o) < r + eps) continue;
                o = calc(2 * (p[j].first - p[i].first),
                         2 * (p[j].second - p[i].second),
                         sqr(p[j].first) + sqr(p[j].second)
                            - sqr(p[i].first) - sqr(p[i].second),
                         2 * (p[k].first - p[i].first),
                         2 * (p[k].second - p[i].second),
                         sqr(p[k].first) + sqr(p[k].second)
                             - sqr(p[i].first) - sqr(p[i].second));
                r = dist(o, p[i]);
            }
        }
    }
    cout << fixed << setprecision(3) << sqrt(r) << endl;
    return 0;
}