【BZOJ1038】[ZJOI2008]瞭望塔 计算几何 半平面交/模拟退火+二分

对于我们不会半平面交的人啊，处理此类题最好的方式还是模拟退火。数据量较大，于是使用二分优化判断过程。这样，虽在时间复杂度上稍逊一筹，但在代码量上可以说是较为优秀的！

确定了思路，后面的问题迎刃而解！

对于瞭望塔所处的位置进行模拟退火，对于每一个位置可通过可行解与其他拐点之间斜率的单调性二分求出瞭望塔高度。

注意由于所求高度可能很大（见以下数据 tower4.in/out），二分上界应设置成 1e11 。

Input:

4

0 1 99999 100000

0 100000 100000 0

Output:

4999900000.000

[ZJOI2008]瞭望塔 C++代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 305
int n;
pair<double,double> p[N];
bool judge(pair<double,double> point)
{
	for(int i=2;i<=n;i++)
		if((point.first-p[i].first)*(point.second-p[i-1].second)>(point.first-p[i-1].first)*(point.second-p[i].second))
			return false;
	return true;
}
double height(double x)
{
	for(int i=2;i<=n;i++)
		if(p[i-1].first<=x&&p[i].first>=x)
			return p[i-1].second+(p[i].second-p[i-1].second)/(p[i].first-p[i-1].first)*(x-p[i-1].first);
	return -1;
}
double divide(double x)
{
	double l=0,r=1e11;
	double mid=(l+r)/2;
	while(r-l>1e-5)
	{
		if(judge(make_pair(x,mid))) r=mid;
		else l=mid;
		mid=(l+r)/2;
	}
	mid-=height(x);
	return mid;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>p[i].first;
	for(int i=1;i<=n;i++)
		cin>>p[i].second;
	double now=(p[1].first+p[n].first)/2,ans,tempans;
	ans=divide(now);
	for(double T=(p[n].first-p[1].first);T>0.00001;T*=0.998)
	{
		double temp=now+T*sin(rand());
		if(temp<p[1].first||temp>p[n].first)
			continue;
		tempans=divide(temp);
		double dE=ans-tempans;
		if(dE>0||exp(dE/T)>abs(sin(rand())))
			now=temp,
			ans=tempans;
	}
	printf("%.3lf\n",ans);
	return 0;
}