https://codeforces.com/contest/1059/problem/D

可恶,都这么接近AC了的,这题嘛,给出n个点(n=1e5)(x,y)(x,y∈[-1e7,1e7]),求最小的R,使存在一个圆:

(x-a)^2+(y-R)^2=R^2 使所有的点都在圆内或者圆上

先说下我的思路:

le=0,ri=1e7,然后二分条件ri-le>1e-8,对于函数ok(mid)

先设一个a的区间[-inf,inf],然后对每个点[x,y]

求出它对a的要求区间[x-sqrt(2*mid*y-y*y),x+sqrt(2*mid*y-y*y)]

将所有区间合并,如果最终区间存在就返回1,否则返回0

 

总体的思路是没问题的

但做这题我犯了好几个错误,说一下

1.首先是二分的范围不对:

答案的范围应该是多少,首先半径不可能是0,所以le是对的

半径最大是怎样呢,半径最大时应该是这样的数据(-1e7,0),(1e7,1)这样的半径有多大呢,我都猜不出来

要么列式计算,要么用代码调出来,但肯定不止1e7这么大

所以ri应该设大点,具体多大可以调,也可以算

 

2.其次,是二分的方法不对

在遇到一些关于高精度的问题时,题目经常会这么问

对此我的二分条件如下

还记得我刚才说ri太小了吧,对此,我估计了一下,ans再怎么大也不会有1e18,哈哈,这下绝对ok了

然而

double 的精度有效数字为12位,1e18的话,精度最大位1e6

这道题目答案的最大值为2e14,所以le和ri的差最小为2e2,所以到最后le和ri的差会一直是2e2>1e-7,

因此二分永远不会结束,

所以搜索条件也得改,题目说答案正确的要求是

好,我的搜索条件也必须是那样,于是搜索条件变成了:

这的确有效,搜索总会在正确的地方停止

 

3.还有一个地方的确是我的思维有了遗漏,我对a的区间的计算公式[x-sqrt(2*mid*y-y*y),x+sqrt(2*mid*y-y*y)]

是根据y>0来算的,然而还有y<0的点,加上如果y>0和y<0的点都有就肯定不存在R,所以y肯定都是1个符号,所以

把y都变成正的是最方便的做法

加一句就ok了

 

最后当然还是A了,

最重要的教训是:搜索条件的改变,二分范围的推敲

以下是代码

//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//输入输出
#define PDD pair<double,double>
#define PII pair<int,int>
#define PB push_back
#define x first
#define y second
using namespace std;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
typedef long long ll;
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint>
inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint>
inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(1e5+5);
double eps = 1e-9;
PDD cor[maxn];
int n;
PDD reach(double R, PDD P)
{
	double s = 2 * R*P.y - P.y*P.y;
	if (s < 0)return { inf,-inf };
	double dx = sqrt(s);
	return { P.x - dx,P.x + dx };
}
PDD inter(PDD A, PDD B)
{
	PDD C(max(A.x, B.x), min(A.y, B.y));
	if (C.x > C.y )return { -1,-1 };
	else return C;
}
bool ok(double R)
{
	PDD res = { -inf,inf };
	RE2(i, n)
	{
		res = inter(res, reach(R, cor[i]));
		if (res.x==-1&&res.y==-1)return 0;
	}
	return 1;
}
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	int T(1), times(0);
#ifdef CPP_IO// CPP_IO
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (++times, T--)
	{
		cin >> n;
		RE2(i, n)cin >> cor[i].x >> cor[i].y;
		bool shang = 0, xia = 0;
		RE2(i, n)
		{
			if (cor[i].y > 0)shang = 1;
			else if (cor[i].y < 0)cor[i].y*=-1,xia = 1;
		}
		if (shang&&xia)
		{
			cout << -1 << endl;continue;
		}
		double toobig = 2e16;
		double le = 0, ri = toobig;
		while (ri-le > max(ri,1.)*1e-7)
		{
			double mid = (le + ri) / 2;
			if (mid < 1)
				mid = mid;
			if (ok(mid))ri = mid;
			else le = mid;
		}
		if (ri == toobig)
		{
			cout << -1 << endl; continue;
		}
		cout <<setprecision(7)<<fixed<< ri << endl;
	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}