现在要在山上的某个部位装一盏灯，使得这座山的任何一个部位都能够被看到。
给出最小的y坐标，如图的+号处就是y坐标最小的安装灯的地方。
这个题嘛...今年省选前学姐来我们（破烂）的机房串门的时候提到了这个题qwq学姐表示十分毒瘤qwq
压了很久今天终于做了qwq
因为问题说的太模糊了233，所以我们首先需要简化一下题意。（开始在如何判断能看到灯的问题上卡了很久）
题目其实说的是：把给出的（相邻的）拐点连成直线，找到一个点的纵坐标，使这个点在所有的直线上方或恰好在直线上。
仔细考虑一下这个其实是有二分单调性的，我们便可以二分要求的纵坐标。
首先我们把所有直线的信息求出（斜率、截距，详见必修2qwq）。
然后在二分答案的判定中，我们可以确定以二分出的答案为坐标的点在各直线上的横坐标。确定横坐标的范围，若横坐标范围是个合法的区间，我们就可以判定有解。
根据必修2的学习，我们知道斜率是一个易错点（逃），判定的时候需要分类讨论斜率大于0小于0等于0的情况（等于0很重要，防止整数被0除）
因为平时一直在做整数域上的二分，所以这次（恰巧打了一下实数域上的二分），这时需要尤其注意精度问题。
实数域二分例 eps用来控制精度，通常可取为1e-8
while(l+eps<r)
{
double mid=(l+r)/;
if(check(mid)) r=mid;
else l=mid;
}
而且在算直线信息的时候还要乘上那个1.0，在强制类型转换。
Code
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<utility> using namespace std;
const double eps=1e-; int n;
pair<int,int>p[];
struct line{
double k,b;
}li[]; bool check(double x)
{
double l=-,r=;
for(int i=;i<n;i++)
{
if(li[i].k<) l=max(l,(x-li[i].b)/li[i].k);
else if(li[i].k>) r=min(r,(x-li[i].b)/li[i].k);
else if(li[i].k==&&li[i].b>x) return ;
}
return l<=r;
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d%d",&p[i].first,&p[i].second);
for(int i=;i<n;i++)
{
li[i].k=1.0*(p[i+].second-p[i].second)/(p[i+].first-p[i].first);
li[i].b=1.0*p[i].second-li[i].k*p[i].first;
}
double l=,r=;
while(l+eps<r)
{
double mid=(l+r)/;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.2lf",l);
return ;
}