题解 P2600 【[ZJOI2008]瞭望塔】

· · 题解

我不会什么半平面交，也不想写队列，我只用最暴力的方法AC此题

首先通过手动模拟可以得到一个结论：

瞭望塔的横坐标一定在两条直线的交点处

所以我们先利用开始的n个点求出n-1条直线

然后两两枚举求交点的横坐标。

对于每一个横坐标再通过枚举n-1条直线求最高点

然后答案取一个最小值即可

复杂度O(n^3)

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef double db;
const int N=305;
const db inf=99999999999.0;
int n;
db ax[N],ay[N];
struct LINE{
    db k,b; //y=kx+b
}ln[N];
db ans=inf;
db sol(db x){ //计算特定横坐标的最小瞭望塔高度
    db res=0;
    for(int i=1;i<n;i++)
        res=max(res,ln[i].k*x+ln[i].b);
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf",&ax[i]);
    for(int i=1;i<=n;i++)
        scanf("%lf",&ay[i]);
    for(int i=1;i<n;i++){
        ln[i].k=(ay[i]-ay[i+1])/(ax[i]-ax[i+1]);
        ln[i].b=ay[i]-ln[i].k*ax[i];
    }
    for(int i=1;i<=n;i++)
        ans=min(ans,sol(ax[i])-ay[i]); //先枚举每个端点
    for(int i=1;i<n;i++)
        for(int j=i+1;j<n;j++){
            db x=(ln[i].b-ln[j].b)/(ln[j].k-ln[i].k); //求两直线的交点
            for(int k=1;k<n;k++)
                if(ax[k]<=x&&x<=ax[k+1])
                    ans=min(ans,sol(x)-ln[k].k*x-ln[k].b); //最小化答案
        }
    printf("%.3lf\n",ans);
    return 0;
}