题解 P1663 【山】
iyanhang
2018-04-13 22:55:59
#### 楼上题解里有纯数学的办法，这里提供一下普遍的二分答案的办法。
### 具体：
* 求出直线的斜率，截距等资料。
* 二分枚举高度y。
* check(mid)函数：如果对于任意一条直线，存在(x,y)在直线的上端或在直线上则true.
* 判断时，通过直线方程求出满足y的点(x0,y)，
1. 对于k>0,则x的解集的右端点取x0.
2. 对于k<0,则左端点取x0.
3. 对于k==0,直接看b和mid的关系.
* 最后(l,+inf)...(-inf,r)等等取交集，即判断return l<=r即可。
```c++
#include <bits/stdc++.h>
using namespace std;
const int MN=5005;
typedef long long ll;
struct line
{
double k,b;
int x1,y1,x2,y2;
void solve()
{
k=((double)(y2-y1))/((double)(x2-x1));
b=(double)y2-k*(double)x2;
}
}l[MN];
/*double cross(line l1,line l2)
{
if (l1.k==l2.k) return 0.00;
return (l1.b*l2.k-l2.b*l1.k)/(l2.k-l1.k);
}*/
int n;
bool check(double x)
{
double L=-2e9,R=2e9;
for (int i=1;i<n;++i)
{
if (l[i].k<0) L=max(L,(x-l[i].b)/l[i].k);
else if (l[i].k>0) R=min(R,(x-l[i].b)/l[i].k);
else if (x<l[i].b) return false;
}
return L<=R;
}
ll read(){
ll f=1,x=0;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main()
{
n=read();
int x1,y1,x2,y2;x1=read();y1=read();
for (int i=2;i<=n;++i)
{
x2=read();y2=read();
l[i-1].x1=x1,l[i-1].y1=y1,l[i-1].x2=x2,l[i-1].y2=y2;
l[i-1].solve();
x1=x2,y1=y2;
}
double L=0.00,R=2e9;
while (L+0.001<=R)
{
double mid=(L+R)/2.00;
if (!check(mid)) L=mid; //don't need to plus 1.
else R=mid;
}
printf("%.2lf",R);
return 0;
}
```