BZOJ1038 [ZJOI2008]瞭望塔

BZOJ1038

正解是模拟退火半平面交

不会。

于是三分。

枚举每一条线段,三分最优点的坐标,然后枚举每条直线计算高度即可。

时间复杂度,其中L为整个区间的长度。

三分的正确性证明


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
#include <iostream>
#include <limits>
#include <iomanip>
#include <algorithm>


const int N = 300;
const long double EPS = 1e-12;


long double x[N], y[N];
int n;


long double calc(double );


int main(void)
{
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> x[i];
    for (int i = 0; i < n; ++i)
        std::cin >> y[i];
   
    long double ans = std::numeric_limits <long double> ::max();
    for (int i = 1; i < n; ++i)
    {
        long double xl = x[i - 1], xr = x[i], yl = y[i - 1], yr = y[i];
        while (xr - xl > EPS)
        {
            long double xd = (xr - xl) / 3, yd = (yr - yl) / 3;
            if (calc(xl + xd) - (yl + yd) > calc(xr - xd) - (yr - yd))
            {
                xl += xd;
                yl += yd;
            }
            else
            {
                xr -= xd;
                yr -= yd;
            }
        }
        ans = std::min(ans, calc(xl) - yl);
    }
   
    std::cout << std::setiosflags(std::ios::fixed) << std::setprecision(3) << ans << std::endl;
   
    return 0;
}


inline long double calc(double p)
{
    long double h = 0;
    for (int i = 0; i < n; ++i)
        h = std::max(h, y[i]);
    for (int i = 1; x[i] < p && i < n; ++i)
        h = std::max(h, y[i] + (y[i] - y[i - 1]) / (x[i] - x[i - 1]) * (p - x[i]));
    for (int i = n - 1; x[i - 1] > p && i >= 0; --i)
        h = std::max(h, y[i] + (y[i] - y[i - 1]) / (x[i] - x[i - 1]) * (p - x[i]));
    return h;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注