H. 山
Description
给一座山，如图所示
现在要在山上的某个部位装一盏灯，使得这座山的任何一个部位都能够被看到。给出最小的 y 坐标，如图的+号处 就是 y 坐标最小的安装灯的地方。
Input
第一行一个数 N，表示这座山有 N 个点构成，接下来 N 行从左到右给出了这座山的构造情况，每行两个数 Xi,Yi， 表示一个折点，保证 Xi>Xi−1（1<i≤N)。
Output
仅输出一行，为最小的 y 坐标，当你的答案与标准答案相差 0.01 时，则被认为是正确的。
Samples
Input 复制
6
0 0
10 0
11 1
15 1
16 0
25 0
Output
3.00
Hint
30%的数据，1≤N≤50;
100%的数据，1≤N≤5000，0≤Xi,Yi≤100000，保证答案不超过1000000。
思路：
说说我被这个题卡的全过程。
首先看到最低高度y，第一反应是二分，感觉有单调性，就打算先莽一发。
那么如何check呢。
我们要找到每条直线与当前枚举高度的交点，比如当直线的斜率小于0时，该点左边的所有点都可以看见。又因为要满足所有直线的要求，对所有斜率小于0的直线取左端点max。
同理，当该直线的斜率大于0时，该点右边的点都可以看见，取右端点的min。
当区间合法时，则该高度合法。
但是这样会漏点斜率为0的情况，特判一下就好了。具体原因画画图就出来了。
几个小tips：
1.注意斜率是y/x
2.注意计算过程中的精度和输出答案的精度是不一样的
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } #define PI acos(-1) const double eps=1e-8; const int maxn=1e6+100; struct node{ double x,y; }a[maxn];///存点 struct node1{ double k,b,x; }b[maxn];///存线段 int n; bool check(double y){ double l=-1e9,r=1e9; for(int i=2;i<=n;i++){ if(b[i].k<0){ double t=(y-b[i].b)/b[i].k; l=max(l,t); } else if(b[i].k>0){ double t=(y-b[i].b)/b[i].k; r=min(r,t); } else if(b[i].k==0&&y<b[i].b) return 0; } if(l<=r) return 1; return 0; } int main() { n=read; rep(i,1,n){ cin>>a[i].x>>a[i].y; if(i>1){ b[i].k=(a[i].y-a[i-1].y)/(a[i].x-a[i-1].x); b[i].b=a[i].y-b[i].k*a[i].x; b[i].x=a[i].x; } } double l=0,r=1e9; double res=0; while((r-l)>eps){ double mid=(l+r)/2; if(check(mid)) res=mid,r=mid-eps; else l=mid+eps; ///cout<<mid<<" "<<l<<" "<<r<<endl; } printf("%.2lf\n",res); return 0; }
![洛谷P3194 [HNOI2008]水平可见直线（计算几何+单调栈）](https://ucc.alicdn.com/pic/developer-ecology/288141e3914546aa9a639ec3958e111b.png?x-oss-process=image/resize,h_160,m_lfit)