瞭望塔

Time Limit: 10 Sec Memory Limit: 162 MB

Description

致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。

我们将H村抽象为一维的轮廓。如下图所示我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状，这里x1 < x2 < …< xn。

瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可以看到H村的任意位置。

可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。

为了节省开支，dadzhi村长希望建造的塔高度尽可能小。请你写一个程序，帮助dadzhi村长计算塔的最小高度。

Input

第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数，为y1 ~ yn。

Output

仅包含一个实数，为塔的最小高度，精确到小数点后三位。

Sample Input

4
　10 20 49 59
　0 10 10 0

Sample Output

14.500

HINT

N ≤ 300，输入坐标绝对值不超过106，注意考虑实数误差带来的问题。

Solution

首先，如果我们确定了一个点的话，显然是可以Check的。

对于 每一个点连向这个点 的连线必须是要逆时针方向的。

那么如果有一个横坐标了，我们就可以二分答案了。怎么确定这个横坐标呢？

乍一看，数据这么小：当然是模拟退火啦！上一波退火美滋滋。٩(๑>◡<๑)۶

Code

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long s64;

const int ONE = 1005;
const double eps = 1e-4;

int n;
double from, to;
double Ans = 1e20;

struct power
{
    double x, y;
}a[ONE];

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int PD(double a, double b)
{
    if(fabs(a - b) <= eps) return 0;
    if(a > b) return 1;
    return -1;
}

double Gety(double x)
{
    for(int i = 2; i <= n; i++)
        if(PD(a[i-1].x, x) <= 0 && PD(x, a[i].x) <= 0)
        {
            double k = (a[i].y - a[i-1].y) / (a[i].x - a[i-1].x);
            double b = a[i-1].y;
            return k * (x - a[i-1].x) + b;
        }
}

double Cross(power a, power b, power c) {return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);}
int Check(power A)
{
    for(int i = 2; i <= n; i++)
        if(PD(Cross(a[i-1], a[i], A), 0) < 0) return 0;
    return 1;
}

double Judge(double x)
{
    double l = 0, r = 1e10, res;
    double y = Gety(x);
    while(l < r - 0.0001)
    {
        double mid = (l + r) / 2;
        if(Check( (power){x, y + mid} )) r = mid;
        else l = mid;
    }
    if(Check( (power){x, y + l} )) res = l; else res = r;
    Ans = min(Ans, res);
    return res;
}

double Random() {return (rand()%1000) / 1000.00;}
void SA(double T)
{
    double Now = (from + to) / 2, A;
    Judge(Now);
    while(T >= 0.0001)
    {
        A = Now + T * (Random() * 2 - 1);
        if(!(from <= A && A <= to)) continue;
        double dE = Judge(Now) - Judge(A);
        if(dE > 0 || Random() <= exp(dE / T))
            Now = A;
        T *= 0.993;
    }

    for(double i = -1; i <= 1; i += 0.001)
        Judge(Now + i);
}

int main()
{
    n = get();
    for(int i = 1; i <= n; i++) scanf("%lf", &a[i].x);
    for(int i = 1; i <= n; i++) scanf("%lf", &a[i].y);


    from = a[1].x;  to = a[n].x;
    SA(to - from);

    printf("%.3lf", Ans);
}