锐客网

  1. 首页 > it技术 > >

#|CodeForces - 1059D Nature Reserve

#二分三分

这道题有两种做法。
首先可以知道有点在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; }

    推荐阅读


    上一篇：进程间通信——DLL共享节

    下一篇：进程间通信——匿名管道