Description

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

Input

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

Output

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

Sample Input

10 20 2 3 3 6 14

Sample Output

3.00

Data Constraint

數據范圍
對 10%的數據n<=10,
?對 30%的數據n<=100
對 100%的數據n<=2000
保證輸入合法，x,y屬于[1,10^6]. 做法：我們發現，如果在任意兩個圓心之間連邊，會有一個“門”，這個門只在其長度 2r時是打開的，其他情況是封閉 的。我們發現問題就變為每個門有一個關閉的時間點，求什么時候起點與終點聯通，這與原問題是等價的。類似于 對偶圖，我們把房間墻壁在起點與終點處斷開，當兩部分墻壁聯通時，顯然起點與終點就斷開了，反之亦然。于是我們可以二分一個r，然后加邊判斷墻壁是否聯通。 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 #define LL long long 6 #define N 3020 7 using namespace std; 8 int n,x,y; 9 double q[N],p[N]; 10 int f[N]; 11 12 void Init(){ 13 scanf("%d%d%d",&x,&y,&n); 14 for (int i=1;i<=n;i++) scanf("%lf%lf",&q[i],&p[i]); 15 } 16 17 double Getdis(int i,int j){ 18 return (q[i]-q[j])*(q[i]-q[j])+(p[i]-p[j])*(p[i]-p[j]); 19 } 20 21 int Find(int x){ 22 if (f[x]==0) return x; 23 f[x]=Find(f[x]); 24 return f[x]; 25 } 26 27 bool Calc(double ain){ 28 memset(f,0,sizeof(f)); 29 for(int i=1;i<=n;i++){ 30 for(int j=i+1;j<=n;j++) 31 if (Getdis(i,j)<=4*ain*ain){ 32 int u=Find(i), v=Find(j); 33 if (u!=v) f[u]=v; 34 } 35 if (q[i]-ain<=0){ 36 int u=Find(i),v=Find(n+1); 37 if (u!=v) f[u]=v; 38 } 39 if (p[i]-ain<=0){ 40 int u=Find(i),v=Find(n+2); 41 if (u!=v) f[u]=v; 42 } 43 if (q[i]+ain>=x){ 44 int u=Find(i),v=Find(n+3); 45 if (u!=v) f[u]=v; 46 } 47 if (p[i]+ain>=y){ 48 int u=Find(i),v=Find(n+4); 49 if (u!=v) f[u]=v; 50 } 51 } 52 int u=Find(n+1),v=Find(n+2); 53 if (u==v) return false; 54 v=Find(n+3); 55 if (u==v) return false; 56 u=Find(n+4); 57 if (u==v) return false; 58 v=Find(n+2); 59 if (u==v) return false; 60 return true; 61 } 62 63 void Work(){ 64 double l=0,r=1000000.0; 65 for(;l+1e-3<r;){ 66 double mid=(l+r)/2; 67 if (Calc(mid)) l=mid; else r=mid; 68 } 69 printf("%.2lf",l); 70 } 71 72 int main(){ 73 freopen("AC.in","r",stdin); 74 freopen("AC.out","w",stdout); 75 Init(); 76 Work(); 77 } View Code

?

轉載于:https://www.cnblogs.com/traveller-ly/p/9794073.html

總結

以上是生活随笔為你收集整理的5904.刺客信条（AC）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。