题解 P1663 【山】
Justin_N_Wu
2017-05-03 17:34:14
如果我们把相邻的两个点连接起来，看作一条条直线，那么我们可以发现我们要求的就是找到一个点，使它在每一条的直线的上方或在直线上，并且要求y坐标越小越好。
首先第一步当然是这n-1条直线的表达式给求出来（别说不会，初二就学过了好吧？）
然后我们会发现，对于我们枚举的每一个高度，对于每一条直线都有一个满足要求的区间，那么我们怎么判断这个高度是否可行？显然，若这些区间有交集的话，那么就是有解了，否则就是不行。
枚举高度我们可以通过二分来实现，剩下就是解一下不等式问题就可以了。
代码如下：
``` cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5005;
struct ad{ int x,y; } a[maxn];
struct line{ double k,b; } b[maxn]; //存直线的表达式
int n; double l,r,mid,L,R,ans;
inline int read(){
int ret=0; char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret;
}
inline bool check(double x){
L=-2e9,R=2e9;
for (int i=1;i<n;i++){
if (b[i].k<0) L=max(L,(x-b[i].b)/b[i].k); //由于k可能小于0，注意不等式两边同除以负数要变号
if (b[i].k>0) R=min(R,(x-b[i].b)/b[i].k);
if (b[i].k==0&&b[i].b>x) return 0; //k等于0的话一除就暴了，注意特判
}
return L<=R;
}
int main(){
freopen("hill.in","r",stdin);
freopen("hill.out","w",stdout);
n=read();
for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
for (int i=1;i<n;i++){
b[i].k=1.0*(a[i].y-a[i+1].y)/(a[i].x-a[i+1].x); //自己推一下的话，应该能懂
b[i].b=1.0*a[i].y-b[i].k*a[i].x;
}
l=0,r=1000000;
while (r-l>=0.001){ //二分小数的办法
mid=(l+r)/2.0;
if (check(mid)) ans=r=mid; else l=mid;
}
printf("%.2lf\n",ans);
return 0;
}
```
#PS 本人第一次写题解，多多见谅