當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

【JZOJ3636】【BOI2012】Mobile(mobile)

發(fā)布時(shí)間：2025/3/15 编程问答 16 豆豆

生活随笔收集整理的這篇文章主要介紹了【JZOJ3636】【BOI2012】Mobile(mobile) 小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

Mission

著名的手機(jī)網(wǎng)絡(luò)運(yùn)營(yíng)商Totalphone 修建了若干基站收發(fā)臺(tái)，以用于把信號(hào)網(wǎng)絡(luò)覆蓋一條新建的高速公路。因?yàn)門(mén)otalphone 的程序員總是很馬虎的，所以，基站的傳功功率不能獨(dú)立設(shè)置，只能將所有新基站的功率設(shè)置為一個(gè)相同的值。為了讓能源的消耗盡量少，公司希望知道公路中任意點(diǎn)到最近基站距離的最大值。

輸入的第一行包括兩個(gè)整數(shù)N（1<=N<=10^6）和L（1<=L<=10^9）分別表示基站收發(fā)臺(tái)的數(shù)量和高速公路的長(zhǎng)度。接下來(lái)N行，每行包含一對(duì)整數(shù)xi,yi（-10^9<=xi,yi<=10^9）描述一個(gè)基站的坐標(biāo)。所有給出的點(diǎn)都互不相同。點(diǎn)按照x坐標(biāo)不下降排列。如果兩個(gè)點(diǎn)的x坐標(biāo)相同，那么它們之間按照y坐標(biāo)的升序排列。

高速公路是一條從(0,0) 到(L,0) 的直線(xiàn)線(xiàn)段。

Solution

先說(shuō)說(shuō)O(n?log)的做法，很顯然出題人是卡這種做法的。
二分答案，然后O(n)掃一遍判斷n個(gè)圓是否覆蓋了高速公路。

考慮到只有兩點(diǎn)之間中垂線(xiàn)與公路交點(diǎn)（或公路端點(diǎn)）才有可能貢獻(xiàn)。
我們利用一個(gè)單調(diào)棧，維護(hù)相鄰的點(diǎn)之間的中垂線(xiàn)與公路交點(diǎn)的橫坐標(biāo)單調(diào)遞增，
最后掃一遍棧內(nèi)元素得出答案。

如圖，那么B點(diǎn)是沒(méi)有用的，因?yàn)槟軌蜇暙I(xiàn)的區(qū)段位于E點(diǎn)之前，D點(diǎn)之后，是空集。

Code

#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #define ll long long #define db double using namespace std; const char* fin="mobile.in"; const char* fout="mobile.out"; const int inf=0x7fffffff; const int maxn=1000007; const db eps=10e-10; int n,m,i,j,k; int equ(db a,db b){return fabs(a-b)<=eps?0:(a>b?1:-1);} struct P{db x,y;P(db _x=0,db _y=0){x=_x;y=_y;}P operator +(P b){return P(x+b.x,y+b.y);}P operator -(P b){return P(x-b.x,y-b.y);}P operator *(db b){return P(x*b,y*b);}db operator ^(P b){return x*b.y-y*b.x;}P per(){return P(y,-x);} }a[maxn],b[maxn],c[maxn]; struct L{P p,v;L(){}L(P _p,P _v){p=_p;v=_v;} }L0;/*P ict(L a,L b){return b.p+b.v*(((a.p-b.p)^a.v)/(b.v^a.v));} P x0(P a,P b){return ict(L(P((a.x+b.x)/2,(a.y+b.y)/2),(b-a).per()),L0);}*/ P x0(P a,P b){return P((b.x*b.x+b.y*b.y-a.x*a.x-a.y*a.y)/2/(b.x-a.x),0);} db dist(P a,P b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}int read(){int x=0,i=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') i=-1;ch=getchar();}while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*i; } int main(){freopen(fin,"r",stdin);freopen(fout,"w",stdout);n=read();m=read();L0=L(P(0,0),P(m,0));int N=0;for (i=1;i<=n;i++){j=read();k=read();if (!N || equ(j*1.0,a[N].x)) a[++N]=P(j,k);else if (abs(k)<fabs(a[N].y)) a[N].y=k;}n=N;db l1=10e10,l2=10e10;P tmp,tmd;N=0;if (n==1){l1=dist(L0.p,a[1]);l2=dist(L0.v,a[1]);}else{b[++N]=a[1];l1=min(l1,dist(L0.p,a[1]));l2=min(l2,dist(L0.v,a[1]));b[++N]=a[2];l1=min(l1,dist(L0.p,a[2]));l2=min(l2,dist(L0.v,a[2]));c[N-1]=x0(a[1],a[2]);for (i=3;i<=n;i++){while (N>1){tmd=x0(b[N],a[i]);if (equ(c[N-1].x,tmd.x)<=0) break;N--;}c[N]=tmd;b[++N]=a[i];l1=min(l1,dist(L0.p,a[i]));l2=min(l2,dist(L0.v,a[i]));}}db ans=max(l1,l2);for (i=1;i<N;i++){if (equ(c[i].x,0.0)>=0 && equ((c[i].x),m*1.0)<=0)ans=max(ans,dist(c[i],b[i]));}printf("%.3lf\n",ans);return 0; }