【JZOJ3636】【BOI2012】Mobile(mobile)

2019-11-06 06:03:22

字體：大中小

來源：轉載

供稿：網友

Mission

著名的手機網絡運營商Totalphone 修建了若干基站收發臺，以用于把信號網絡覆蓋一條新建的高速公路。因為Totalphone 的程序員總是很馬虎的，所以，基站的傳功功率不能獨立設置，只能將所有新基站的功率設置為一個相同的值。為了讓能源的消耗盡量少，公司希望知道公路中任意點到最近基站距離的最大值。

輸入的第一行包括兩個整數N（1<=N<=10^6）和L（1<=L<=10^9）分別表示基站收發臺的數量和高速公路的長度。接下來N行，每行包含一對整數xi,yi（-10^9<=xi,yi<=10^9）描述一個基站的坐標。所有給出的點都互不相同。點按照x坐標不下降排列。如果兩個點的x坐標相同，那么它們之間按照y坐標的升序排列。

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

Solution

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

考慮到只有兩點之間中垂線與公路交點（或公路端點）才有可能貢獻。我們利用一個單調棧，維護相鄰的點之間的中垂線與公路交點的橫坐標單調遞增，最后掃一遍棧內元素得出答案。這里寫圖片描述如圖，那么B $B$ 點是沒有用的，因為能夠貢獻的區段位于E $E$ 點之前，D $D$ 點之后，是空集。

Code

#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<math.h>#define ll long long#define db doubleusing 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])); } Warning

1.卡常 1)求交時請一步得解，不要用什么向量求交。 2)讀入優化。