七牛云建网站,新冠最新消息实时数据,团购网站 方案,禁止wordpress自动更新链接#xff1a;CodeForces - 1059D 题意#xff1a;给出笛卡尔坐标系上 n 个点#xff0c;求与 x 轴相切且覆盖了所有给出点的圆的最小半径。 题解#xff1a;二分半径即可。判断#xff1a;假设当前二分到的半径是 R #xff0c;因为要和 x 轴相切#xff0c;所以圆心…链接CodeForces - 1059D 题意给出笛卡尔坐标系上 n 个点求与 x 轴相切且覆盖了所有给出点的圆的最小半径。 题解二分半径即可。判断假设当前二分到的半径是 R 因为要和 x 轴相切所以圆心一定在 y R 上对于每一个点而言圆要覆盖该点那么圆心在 y R 上一定有一段限定区间所以只要判断这 n 个区间是否有公共区间即可。卡点误差太可恶了求区间段时应该将 sqrt(R * R - d * d) 写成 sqrt(R - d) * sqrt(R d) 否则误差特别大。 #include bits/stdc.h
using namespace std;const double EPS 1e-6;
const double INF 1e17;
const int mod 1e9 7;
const int maxn 1e5 10;
int n;
double x[maxn], y[maxn];bool judge(double R)
{double l -INF, r INF;for(int i 0; i n; i){double d fabs(y[i] - R);if(d R) return false;//不可以写成sqrt(R * R - d * d),这样误差会加大double k sqrt(R - d) * sqrt(R d);double a x[i] - k, b x[i] k;if(a r || b l) return false;l max(l, a);r min(r, b);}return true;
}bool OK()
{bool z false, f false;for(int i 1; i n; i){if(y[i] 0) z true;else if(y[i] 0) f true;}return !(z f);
}int main()
{scanf(%d, n);for(int i 0; i n; i) scanf(%lf%lf, x[i], y[i]);if(!OK())return puts(-1) 0;for(int i 0; i n; i) y[i] fabs(y[i]);double l 0, r INF;for(int i 0; i 100; i){double mid (l r) / 2.0;if(judge(mid)) r mid;else l mid;}printf(%.6f\n, r);return 0;
} 转载于:https://www.cnblogs.com/chenquanwei/p/9766049.html
