题目

著名的手机网络运营商Totalphone 修建了若干基站收发台，以用于把信号网络覆盖一条新建的高速公路。因为Totalphone 的程序员总是很马虎的，所以，基站的传功功率不能独立设置，只能将所有新基站的功率设置为一个相同的值。为了让能源的消耗尽量少，公司希望知道公路中任意点到最近基站距离的最大值。

题解

这条线段应该被分成一些部分， 每一部分到中的所以点的最近点为同一个点。 对于相邻的两个点来说， 它们的垂直平分线就是分界线，也就是说：这条线的左边到左边的那个点更近一些，线的右边到右边的点更近。

那么，我们就可以通过垂直平分线就这条线段分成若干个部分。 但是，有一些点是没有用的，就是说这个点和它相邻的两个点的垂直平分线的交点在x轴的上方。 通过这个特性，我们利用单调栈维护一些有用的点，去的那些没有意义的点。

对于两个点的垂直平分线的解析式求法： 两条互相垂直的线的k的乘积为-1， 两点连线的中点横纵坐标为两点横纵坐标的平均数。 这样我们可以求出两个点垂直平分线的解析式。

code

#include<iostream> #include<cmath> #include<cstring> #include<cstdio> #include<algorithm> #define N 1000003 #define ll long long #define db double using namespace std; struct arr { ll x,y; }a[N]; ll n,x,y,tot,z[N],last,yy; db m,ans,sum,t; db gg(db x,db y,db xx,db yy) { return sqrt((xx-x)*(xx-x)*1.0+(yy-y)*(yy-y)*1.0); } db get(db x,db y,db xx,db yy) { if(y==yy)return (x+xx)/2; db k=(xx-x)/(y-yy),tx=(xx+x)*1.0/2,ty=(yy+y)*1.0/2; db b=ty-k*tx; return -b/k; } int main() { freopen("mobile.in","r",stdin); freopen("mobile.out","w",stdout); scanf("%lld%lf",&n,&m); scanf("%lld%lld",&last,&yy);yy=abs(yy); for(int i=2;i<=n;i++) { scanf("%lld%lld",&x,&y); if(x!=last) { a[++tot].x=last; a[tot].y=yy; last=x; yy=abs(y); }else yy=min(yy,abs(y)); } a[++tot].x=last; a[tot].y=yy; z[0]=z[1]=1; for(int i=2;i<=tot;i++) { while(z[0]>1 && get(a[z[z[0]]].x,a[z[z[0]]].y,a[z[z[0]-1]].x,a[z[z[0]-1]].y)>=get(a[z[z[0]]].x,a[z[z[0]]].y,a[i].x,a[i].y))z[0]--; if(z[0]==1) { if(gg(a[z[1]].x,a[z[1]].y,0,0)>gg(a[i].x,a[i].y,0,0))z[1]=i;else if(get(a[z[z[0]]].x,a[z[z[0]]].y,a[i].x,a[i].y)<=m)z[++z[0]]=i; }else if(get(a[z[z[0]]].x,a[z[z[0]]].y,a[i].x,a[i].y)<=m)z[++z[0]]=i; } sum=9223372036854775800; for(int i=1;i<=tot;i++) sum=min(sum,gg(0,0,a[i].x,a[i].y)); ans=sum; sum=9223372036854775800; for(int i=1;i<=tot;i++) sum=min(sum,gg(m,0,a[i].x,a[i].y)); ans=max(ans,sum); for(int i=1;i<z[0];i++) ans=max(ans,gg(get(a[z[i]].x,a[z[i]].y,a[z[i+1]].x,a[z[i+1]].y),0,a[z[i]].x,a[z[i]].y)); printf("%.6lf",ans); }