【BOI2012】Mobile

2019-11-06 07:29:24

字体：大中小

来源：转载

供稿：网友

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

Solution

这道题一眼可以二分，但是发现时间限制在500ms，所以过不了。然后发现可以用中垂线来做，但是没有仔细的去想。正解也就是用中垂线来做。两个点的中垂线，线的左边离左边的点较近，线的右边离右边的点较近。那么当a,b,c组成两组边的中垂线划出来的时候，他们与x轴的交点分别为l，r（假设l< r），那么很明显的l到r之间的点都不会是答案，因为中间的点会离b较近，但是那样的答案就会更小。然后我们现在就可以找到一段区间应该去那些点最优，那么可以用一个队列来做。 1、如果队首和它后面的点的中垂线在x轴的截距＜0，那么队首就退队 2、如果队尾和它前面的点的中垂线，然后要入队的i后队末的中垂线，如果两条线在穿过x轴才相交的话，那么队尾的那个点就没有用了。然后直接求答案就好了。一开始要把点处理一下，比如x相同，取y绝对值最小的。然后两边的端点的值的贡献，一开始就要考虑。

Code

#include<iostream>#include<stdio.h>#include<algorithm>#include<math.h>#include<string.h>#define fo(i,a,b) for(i=a;i<=b;i++)#define db doubleusing namespace std;const int maxn=1e6+7;int i,j,t,n,tot,tou,num,d[maxn];db x[maxn],y[maxn],k,l,u,v,m;db ans,ans1;db sqr(db x){return x*x;}db ju(db x,db y,db xx,db yy){return sqrt(sqr(x-xx)+sqr(y-yy));}db suan(int a,int b){ db k1,k2,b1,b2; return 0.5*(sqr(x[a])+sqr(y[a])-sqr(x[b])-sqr(y[b]))/(x[a]-x[b]);}int get(){ char ch=getchar();int x=0,f=1; 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;}int main(){ freopen("mobile.in","r",stdin); freopen("mobile.out","w",stdout);// freopen("fan.in","r",stdin); scanf("%d%lf",&n,&m); fo(i,1,n){ // scanf("%lf%lf",&k,&l); k=get(),l=get(); if(u!=k){ if(i>1)x[++num]=u,y[num]=v; u=k,v=fabs(l); } else v=min(fabs(l),v); } x[++num]=u,y[num]=v; fo(i,1,num){ db o=sqrt(x[i]*x[i]+y[i]*y[i]); if(i==1)ans1=o; else ans1=(ans1<o)?ans1:o; } ans=ans1; fo(i,1,num){ db o=sqrt(sqr(m-x[i])+y[i]*y[i]); if(i==1)ans1=o; else ans1=(ans1<o)?ans1:o; } ans=max(ans,ans1); tou=1; fo(i,1,num){ while(tou<tot&&suan(d[tou],d[tou+1])<0)++tou; while(tou<tot&&suan(d[tot-1],d[tot])>suan(d[tot],i))--tot; d[++tot]=i; } fo(i,tou+1,tot){ db o=suan(d[i-1],d[i]); if(o>m)break; o=sqrt(sqr(x[d[i]]-o)+sqr(y[d[i]])); ans=(ans>o)?ans:o; } PRintf("%.5lf/n",ans);}

上一篇：《懒人Shell脚本》之八——定期备份Mysql数据库表的实现

下一篇：uva 147 Dollars （dp）