[ CodeForces 1059 D ] Nature Reserve

\(\\\)

\(Description\)

你现在有\(N\)个分布在二维平面上的整点\((x_i,y_i)\)，现在需要你找到一个圆，满足：

能够覆盖所有的给出点
与\(x\)轴相切

现在需要你确定合法的圆的最小半径是多少，精度误差允许在\(10^{-6}\)范围内。

如果不存在一个合法的圆，输出\(-1\)。

\(N\in [1,10^5]，x_i,y_i\in [10^{-7},10^7]\)

\(\\\)

\(Solution\)

垃圾 \(Double\) 毁我青春

首先考虑哪些情况不合法。显然如果点全部在\(x\)轴同一侧显然有解，所以只需要判断所有\(y_i\)是否同号即可。

便于处理，我们将所有点都放到\(x\)轴上方。

然后注意到如果一个半径较小的圆合法，那么半径比他大的圆一定也存在一个合法的位置，于是我们在实数域上二分。设当前二分到的半径为\(K\)，那么显然圆的纵坐标就是\(K\)了，设圆的横坐标为\(X\)。

那么对于一个点\(i\)，该点在这个圆内当且仅当

\[(x_i-X)^2+(y_i-K)^2\le K^2
\]

稍作变形有

\[|x_i-X|\le \sqrt{K^2-(y_i-K)^2}
\]

即可得到对于该点来说，半径为\(K\)的圆合法的\(X\)对于范围：

\[\Delta=\sqrt{K^2-(y_i-K)^2}\ ,\ X\in[x_i-\Delta,x_i+\Delta]
\]

然而并不对。注意到\(\Delta\)可以进一步化简：

\[\Delta=\sqrt{K^2-(y_i-K)^2}=\sqrt{K^2-(y_i^2+K^2-2Ky_i)}=\sqrt{2Ky_i-y_i^2}
\]

看起来没什么不同？假的！下面我们就会谈到二分的范围，\(K^2\)是会爆掉 \(Double\) 的。

用了 \(Long\ Double\) 还是过不了？前面的式子精度会爆炸，精度丢失远高于后面的式子。

\(\\\)

然后二分边界就是对于所有点当前半径的合法区间的交集不为空。

这个部分可以维护最大的 \(L\) 和最小的 \(R\) ，直接判断 \(R>L\) 即可。

当时NC想什么差分数组区间标记前缀和，判断最大权是否为N

\(\\\)

然后讨论二分区间。极限数据两点分布于\((-10^7,1)\)和\((10^7,1)\)，此时半径有\(5\times10^{13}\)之大！

所以二分上界设的大一点不虚\((10^{18}\)之类的\()\)。

\(\\\)

然后还有一个细节。注意\(\Delta\)计算的时候根号下的部分。

必须保证\(2Ky_i-y_i^2\ge 0\)，也就是\(2K\ge y_i\)，不加这一个特判，负数开根右转自闭......

\(\\\)

\(Code\)

#include<cmath>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define R register

#define gc getchar

#define N 100010

using namespace std;

bool f=0;

const double eps=1e-8;

int n;

struct point{double x,y;}p[N];

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

inline bool valid(double x){

  double l=-(double)1e18,r=(double)1e18,dlt;

  for(R int i=1;i<=n;++i){

  	if(p[i].y>x+x) return 0;

    dlt=sqrt(p[i].y*(2*x-p[i].y));

    l=max(l,p[i].x-dlt); r=min(r,p[i].x+dlt);

  }

  return (r-l+eps>=0.0);

}

int main(){

  n=rd();

  for(R int i=1;i<=n;++i){

    p[i].x=(double)rd();

    p[i].y=(double)rd();

    if(p[i].y<0.0) f=1;

  }

  if(f==1) for(R int i=1;i<=n;++i){

      p[i].y=-p[i].y;

      if(p[i].y<0.0) {puts("-1");return 0;}

  }

  int t=0;

  R double l=0.0,r=(double)1e18,mid;

  while(t<=300){

    mid=(l+r)/2.0; ++t;

    valid(mid)?r=mid:l=mid;

  }

  printf("%.10lf",l);

  return 0;

}

巴特西

[ CodeForces 1059 D ] Nature Reserve

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章