cf1059D. Nature Reserve(三分)

题意

Sol

欲哭无泪啊qwq。。。。昨晚一定是智息了qwq

说一个和标算不一样做法吧。。

显然\(x\)轴是可以三分的，半径是可以二分的。

恭喜你获得了一个TLE的做法。。

然后第二维的二分是没有必要的，直接拿圆的标准方程推一下取个最大值就行了。。。。。昨晚没想到qwq给数学老师丢脸了。。

#include<cstdio>

#include<cmath>

#include<algorithm>

#define double long double

using namespace std;

const double eps = 1e-7, INF = 1e18;

const int MAXN = 1e5 + 10;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();

    return x * f;

}

int N, up, down;

double max(double a, double b) {return a > b ? a : b;}

double min(double a, double b) {return a < b ? a : b;}

struct Node {

    double x, y;

}a[MAXN];

int check(int x, int y) {

    if(x < 0 && y > 0) return 1;

    else return 0;

}

double mxr;

double sqr(double x) {

	return x * x;

}

double f(double x) {

    double mx = 0;

    for(int i = 1; i <= N; i++)

    	mx = max(mx, fabs((sqr(a[i].x - x) + sqr(a[i].y)) / (2.0 * a[i].y)));

	return mx;

}

int main() {

    N = read();

    double L = INF, R = -INF;

    for(int i = 1; i <= N; i++) {

        a[i].x = read(), a[i].y = read();

        up = min(up, a[i].y);

		mxr = max(a[i].y, mxr);

        L = min(a[i].x, L);

        R = max(a[i].x, R);

    }

	if(check(up, mxr)) {puts("-1"); return 0;}

	mxr = INF;

    if(up < 0) for(int i = 1; i <= N; i++) a[i].y = -a[i].y;

    int tim = 100;

	while(tim--) {

        double x = (2 * L + R) / 3, y = (L + 2 * R) / 3;

        f(x) < f(y) ? R = y : L = x;

      //  printf("%Lf %Lf\n", f(x), f(y));

    }

    printf("%.10Lf", f(L));

    return 0;

}

巴特西

cf1059D. Nature Reserve(三分)

题意

Sol

最新文章

热门文章