这道题有两种做法。
首先可以知道有点在x x x 轴异侧是不合法的。
Solution 1 二分枚举半径r r r。
半径定了之后，最终的圆心的纵坐标就定了。接下来考虑每个点，以每个点为圆心以r r r 为半径交直线y = r y=r y=r 于两点，这两点的区间就是圆心可取的区间。然后每个点的区间取一个交集就行了。
但是因为c h e c k check check 函数时间太大好像不能直接过。（其实就是写的丑）
另外为了精度，减少乘法即x 2 ? y 2 = ( x + y ) ( x ? y ) x^2-y^2=(x+y)(x-y) x2?y2=(x+y)(x?y)。
Solution 2 【#|CodeForces - 1059D Nature Reserve】三分圆心的横坐标。大佬写得很清楚 链接。
My Code
#include
#include
#include
using namespace std;
const int N = 1e5 + 5;
const double eps = 1e-10;
int n;
double x[N], y[N];
int read() {
int x = 0, f = 1;
char s;
while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;
while(s >= '0' && s <= '9') x = (x << 1) + (x << 3) + (s ^ 48), s = getchar();
return x * f;
}bool cmp(const double x, const double y) {return x - y > eps;
}bool ok(const double r) {
if(n == 1) return cmp(r, y[1] / 2);
if(cmp(fabs(r - y[1]), r)) return 0;
double d = sqrt((r + fabs(r - y[1])) * (r - fabs(r - y[1]))), L = x[1] - d, R = x[1] + d, q, p;
for(int i = 2;
i <= n;
++ i) {
if(cmp(fabs(r - y[i]), r)) return 0;
d = sqrt((r + fabs(r - y[i])) * (r - fabs(r - y[i])));
q = x[i] - d;
p = x[i] + d;
if(cmp(q, R) || cmp(L, p)) return 0;
L = max(L, q);
R = min(R, p);
}
return 1;
} int main() {
double l = 0, r = 1e14, mid, ans = -1;
int times = 100, tot1 = 0, tot2 = 0;
n = read();
for(int i = 1;
i <= n;
++ i) {
x[i] = read(), y[i] = read();
if(y[i] > 0) ++ tot1;
else ++ tot2;
}
if(tot1 && tot2) return puts("-1"), 0;
for(int i = 1;
i <= n;
++ i) if(y[i] < 0.0) y[i] = -y[i];
while(r - l > eps) {
mid = (l + r) / 2;
-- times;
if(ok(mid)) r = mid, ans = mid;
else l = mid;
if(! times) break;
}
printf("%f\n", ans);
return 0;
}
推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值
- win10|搏一搏 单车变摩托，是时候捣鼓一下家中的小米电视机啦。