【bzoj1038】瞭望塔

2015.05.25 09:25 Mon | 17次阅读 | 旧日oi | 固定链接 | 源码

这题还是粘原题吧,不好叙述。。

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

【输入样例一】
6
1 2 4 5 6 7
1 2 2 4 2 1
【输入样例二】
4
10 20 49 59
0 10 10 0

Sample Output

【输出样例一】
1.000
【输出样例二】
14.500

HINT

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

题解

正解是半平面交……但是模拟退火可以过。
随机选取一个位置x,高度用二分check,所有点都会被见到的条件就是这个点和所选点之间的连线在上一个点和所选点之间连线的顺时针方向,这个我们叉积搞一下就好了。

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 305
int n;
double ans,minn=23333333333333333ll;
struct Point{
    double x,y;
    Point(double _,double __):x(_),y(__){}
    Point(){}
    Point operator +(const Point &a)const{
        return Point(x+a.x,y+a.y);
    }
    Point operator -(const Point &a)const{
        return Point(x-a.x,y-a.y);
    }
    double operator *(const Point &a)const{
        return x*a.y-y*a.x;
    }
}p[N];
struct Line{
    Point p1,p2;
    double k,b;
    Line(Point _,Point __):p1(_),p2(__)
    {
        k=(p2.y-p1.y)/(p2.x-p1.x);
        b=p1.y-k*p1.x;
    }
    Line(){}
}line[N];
double Rand()
{
    return rand()%1000/1000.0;
}
bool judge(Point x)
{
    for(int i=2;i<=n;i++)
    if((p[i-1]-x)*(p[i]-x)<0) return 0;
    return 1;
}
double f(double x1)
{
    for(int i=1;i<n;i++) 
    if(line[i].p1.x<=x1&&line[i].p2.x>=x1) 
    return line[i].k*x1+line[i].b;
}
double jud(double x)
{
    double l=0,r=1e11,mid,tmp;
    while(r-l>1e-7)
    {
        mid=(l+r)/2;
        if(judge(Point(x,mid))) tmp=r=mid;
        else l=mid;
    }
    tmp-=f(x);
    if(tmp<minn) minn=tmp,ans=x;
    return tmp;
}
void monitui_fire(double T)
{
    double now=ans;
    for(;T>0.00001;T*=0.99)
    {
        double tmp=now+T*(Rand()*2-1);
        if(tmp<p[1].x||tmp>p[n].x) continue;
        double dE=jud(now)-jud(tmp);
        if(dE>0||exp(dE/T)>Rand()) now=tmp;
    }
    for(int i=1;i<=1000;i++)
    {
        double tmp=ans+T*(Rand()*2-1);
        if(tmp<p[1].x||tmp>p[n].x) continue;
        jud(tmp);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lf",&p[i].x);
    for(int i=1;i<=n;i++) scanf("%lf",&p[i].y);
    for(int i=1;i<n;i++) line[i]=Line(p[i],p[i+1]);
    ans=(p[1].x+p[n].x)/2;
    monitui_fire(p[n].x-p[1].x);
    printf("%.3lf",minn);
}```