Description

故事發(fā)生在1486 年的意大利，Ezio 原本只是一個文藝復興時期的貴族，后來因為家族成員受到圣殿騎士的殺害，決心成為一名刺客。最終，憑借著他的努力和出眾的天賦，成為了杰出的刺客大師。刺客組織在他的帶領下，為被剝削的平民聲張正義，趕跑了原本統(tǒng)治意大利的圣殿騎士首領-教皇亞歷山大六世。在他的一生中，經(jīng)歷了無數(shù)次驚心動魄、扣人心弦的探險和刺殺。
這次的故事就是他暗殺一位作惡多端的紅衣主教。紅衣主教可以吸取他周圍人的生命力量，而他的紅衣教徒也擁有這個力量。紅衣主教的家是一個x*y 的長方形房間，也就是說，他的家的四個角坐標分別為(0,0)(x,0)(0,y)(x,y)。教堂的門在（0，0） ,而紅衣主教就在 （x,y）的臥室休息。他的家中還有n個守護著他的紅衣教徒，站在(ai,bi)。Ezio想要趁主教休息時，從門進入潛入到他的臥室刺殺他，因為主教休息時會脫下紅衣，這樣吸取生命的力量就消失了。可是守衛(wèi)他的紅衣教徒依然很危險，離紅衣教徒太近就會被吸取生命。因此，Ezio想知道，在能刺殺主教的前提，從門到他的臥室的路上，他最遠和離他最近的紅衣教徒保持多遠的距離。注意：教徒都在房間里。

Input

第一行三個整數(shù)x,y,n。之后n行，每行兩個整數(shù)ai，bi ,意義見題目描述。

Output

一行一個數(shù)D，表示Ezio能保持的最大距離，保留兩位小數(shù)。

Sample Input

10 20 2
3 3
6 14

Sample Output

3.00

樣例說明
貼著墻走

Data Constraint

數(shù)據(jù)范圍
對 10%的數(shù)據(jù)n<=10,
對 30%的數(shù)據(jù)n<=100
對 100%的數(shù)據(jù)n<=2000
保證輸入合法，x,y屬于[1,10^6].

Solution

• 先二分答案，轉(zhuǎn)化成判斷性問題。

• 把能連通的點用并查集并起來（下右邊界看成一點，上左邊界看成一點），

• 若最后邊界并在一起了則二分上界下調(diào)，否則下界上調(diào)。

• 注意一下精度問題即可。

• 理論復雜度 $O(n^{2}logn?\alpha (n))$ ，實際上中途退出情況很多，跑得很快。

Code

#include<cstdio> #include<algorithm> #include<cctype> using namespace std; typedef long long LL; const int N=2005; struct data {int x,y; }a[N]; int n,m,k; double ans; int f[N],size[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool cmp(data x,data y) {return x.x<y.x || x.x==y.x && x.y<y.y; } inline int max(int x,int y) {return x>y?x:y; } inline int get(int x) {return f[x]==x?x:f[x]=get(f[x]); } inline void merge(int x,int y) {int xx=get(x),yy=get(y);if(xx^yy){if(size[xx]<size[yy]) swap(xx,yy);f[yy]=xx;size[xx]+=size[yy];} } inline bool check(double x) {for(int i=1;i<=k+4;i++) size[f[i]=i]=1;merge(k+1,k+2);merge(k+3,k+4);for(int i=1;i<=k;i++){if(a[i].y<x) merge(i,k+1);if(m-a[i].y<x) merge(i,k+3);if(a[i].x<x) merge(i,k+4);if(n-a[i].x<x) merge(i,k+2);}double dis=x*x*4;for(int i=1;i<=k;i++)for(int j=i+1;j<=k;j++){LL num=((LL)a[j].x-a[i].x)*(a[j].x-a[i].x);if(num>=dis) break;num+=((LL)a[j].y-a[i].y)*(a[j].y-a[i].y);if(num<dis) merge(i,j);if(get(k+2)==get(k+3)) return false;}return true; } int main() {freopen("AC.in","r",stdin);freopen("AC.out","w",stdout);n=read(),m=read(),k=read();for(int i=1;i<=k;i++) a[i].x=read(),a[i].y=read();sort(a+1,a+1+k,cmp);if(a[1].x+a[1].y==0) return 0&puts("0.00");int l=1,r=max(n,m)*300;while(l<=r){int mid=l+r>>1;if(check(mid*0.003)){l=mid+1;ans=mid*0.003;}else r=mid-1;}printf("%.2lf",ans);return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JZOJ 5904. 【NOIP2018模拟10.15】刺客信条（AC）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。