瞭望塔
Time Limit: 10 Sec Memory Limit: 162 MB
[Submit][Status][Discuss]
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
10 20 49 59
0 10 10 0
Sample Output
14.500
HINT
N ≤ 300，输入坐标绝对值不超过106，注意考虑实数误差带来的问题。
Solution
首先，如果我们确定了一个点的话，显然是可以Check的。
对于 每一个点连向这个点 的连线 必须是要逆时针方向的。
那么如果有一个横坐标了，我们就可以二分答案了。怎么确定这个横坐标呢？
乍一看，数据这么小：当然是模拟退火啦！上一波退火美滋滋。٩(๑>◡<๑)۶
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
using namespace std;
typedef unsigned long long s64; const int ONE = ;
const double eps = 1e-; int n;
double from, to;
double Ans = 1e20; struct power
{
double x, y;
}a[ONE]; int get()
{
int res,Q=; char c;
while( (c=getchar())< || c>)
if(c=='-')Q=-;
if(Q) res=c-;
while((c=getchar())>= && c<=)
res=res*+c-;
return res*Q;
} int PD(double a, double b)
{
if(fabs(a - b) <= eps) return ;
if(a > b) return ;
return -;
} double Gety(double x)
{
for(int i = ; i <= n; i++)
if(PD(a[i-].x, x) <= && PD(x, a[i].x) <= )
{
double k = (a[i].y - a[i-].y) / (a[i].x - a[i-].x);
double b = a[i-].y;
return k * (x - a[i-].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 = ; i <= n; i++)
if(PD(Cross(a[i-], a[i], A), ) < ) return ;
return ;
} double Judge(double x)
{
double l = , r = 1e10, res;
double y = Gety(x);
while(l < r - 0.0001)
{
double mid = (l + r) / ;
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.00;}
void SA(double T)
{
double Now = (from + to) / , A;
Judge(Now);
while(T >= 0.0001)
{
A = Now + T * (Random() * - );
if(!(from <= A && A <= to)) continue;
double dE = Judge(Now) - Judge(A);
if(dE > || Random() <= exp(dE / T))
Now = A;
T *= 0.993;
} for(double i = -; i <= ; i += 0.001)
Judge(Now + i);
} int main()
{
n = get();
for(int i = ; i <= n; i++) scanf("%lf", &a[i].x);
for(int i = ; i <= n; i++) scanf("%lf", &a[i].y); from = a[].x; to = a[n].x;
SA(to - from); printf("%.3lf", Ans);
}