比赛 20160309 评测结果 AAAAAAAAAA
题目名称 拯救小云公主 最终得分 100
用户昵称 zys 运行时间 1.217 s
代码语言 C++ 内存使用 69.48 MiB
提交时间 2016-03-09 21:44:16
显示代码纯文本
  1. #define MAXN 3010
  2.  
  3. #include<cmath>
  4. #include<cstdio>
  5.  
  6. using namespace std;
  7.  
  8. int n,m,boss;
  9. const double eps=1e-5;
  10. int father[MAXN],f1,f2;
  11. double L,R,mid,dis[MAXN][MAXN],Ans;
  12. int up,left,right,low,first[MAXN],s;
  13.  
  14. struct Point{
  15. double x,y;
  16. }pos[MAXN];
  17.  
  18. inline double Dis(Point a,Point b)
  19. {
  20. return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  21. }
  22.  
  23. inline int getf(int x)
  24. {
  25. if(father[x]==x)return x;
  26. father[x]=getf(father[x]);
  27. return father[x];
  28. }
  29.  
  30. inline bool Check()
  31. {
  32. for(int i=1;i<=boss+4;i++)
  33. father[i]=i;
  34. for(int i=1;i<=boss;i++)
  35. for(int j=i+1;j<=boss;j++)
  36. if(dis[i][j]<mid*2.0-eps){
  37. f1=getf(i+4);f2=getf(j+4);
  38. if(f1!=f2)father[f1]=f2;
  39. }
  40. for(int i=1;i<=boss;i++){
  41. if(pos[i].y-1.00<mid-eps){
  42. f1=getf(low);f2=getf(i+4);
  43. if(f1!=f2)father[f1]=f2;
  44. }
  45. if(pos[i].x-1.00<mid-eps){
  46. f1=getf(left);f2=getf(i+4);
  47. if(f1!=f2)father[f1]=f2;
  48. }
  49. if((double)(m)-pos[i].y<mid-eps){
  50. f1=getf(up);f2=getf(i+4);
  51. if(f1!=f2)father[f1]=f2;
  52. }
  53. if((double)(n)-pos[i].x<mid-eps){
  54. f1=getf(right);f2=getf(i+4);
  55. if(f1!=f2)father[f1]=f2;
  56. }
  57. }
  58. if(getf(up)==getf(low))return false;
  59. if(getf(left)==getf(low))return false;
  60. if(getf(up)==getf(right))return false;
  61. if(getf(left)==getf(right))return false;
  62. return true;
  63. }
  64.  
  65. int main()
  66. {
  67. freopen("dis.in","r",stdin);
  68. freopen("dis.out","w",stdout);
  69. scanf("%d%d%d",&boss,&n,&m);
  70. for(int i=1;i<=boss;i++)
  71. scanf("%lf%lf",&pos[i].x,&pos[i].y);
  72. for(int i=1;i<=boss;i++){
  73. dis[i][i]=0;
  74. for(int j=i+1;j<=boss;j++)
  75. dis[i][j]=dis[j][i]=Dis(pos[i],pos[j]);
  76. }
  77. up=1;low=2;left=3;right=4;
  78. L=0;R=1e3;Ans=0;
  79. while(R-L>eps){
  80. mid=(L+R)/2;
  81. if(Check())Ans=mid,L=mid;
  82. else R=mid;
  83. }
  84. printf("%0.2lf",Ans);
  85. }