JZOJ5904 刺客信条

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].

Solution

　　二分答案mid，如果两个教徒之间的距离小于2*mid就联通，用并查集维护连通性，当两部分墙壁联通时，显然起点与终点就断开了。

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 double a[3000],b[3000],x,y;
 5 int n,c[3000]; 
 6 
 7 int find(int s){
 8     if (c[s]==s)
 9         return s;
10     c[s]=find(c[s]);
11     return c[s];
12 }
13 
14 bool check(double s){
15     for (int i=1;i<=n+4;i++)
16         c[i]=i;
17     for (int i=1;i<=n;i++)
18         for (int j=i+1;j<=n+4;j++)
19             if (i!=j){
20                 if (j==n+1&&a[i]<=s){
21                     int xx=find(i),yy=find(j);
22                     c[xx]=yy;
23                 }
24                 if (j==n+2&&a[i]>=x-s){
25                     int xx=find(i),yy=find(j);
26                     c[xx]=yy;
27                 }
28                 if (j==n+3&&b[i]<=s){
29                     int xx=find(i),yy=find(j);
30                     c[xx]=yy;
31                 }
32                 if (j==n+4&&b[i]>=y-s){
33                     int xx=find(i),yy=find(j);
34                     c[xx]=yy;
35                 }
36                 if (j<=n&&(a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])<=s*s*4){
37                     int xx=find(i),yy=find(j);
38                     c[xx]=yy;
39                 }
40             }
41     int x1=find(n+1),x2=find(n+2),x3=find(n+3),x4=find(n+4);
42     if (x1==x2||x3==x4||x1==x3||x2==x4)
43         return true;
44     return false;
45 }
46 
47 int main(){
48     scanf("%lf%lf%d",&x,&y,&n);
49     for (int i=1;i<=n;i++)
50         scanf("%lf%lf",&a[i],&b[i]);
51     double l=0,r=sqrt(x*x+y*y);
52     while (l<=r){
53         double mid=(l+r)/2;
54         if (check(mid))
55             r=mid;
56         else l=mid+0.001;
57         if (r-l<=0.001) break;
58     }
59     printf("%.2lf
",l);
60 }

View Code