上次模拟赛原本的 t1 是这道... 然而我觉得模拟赛的 t1 更难 emm

Problem

https://www.luogu.org/problemnew/show/CF1059D

Solution

判无解情况，在只有一个点的情况发现是一个跟横坐标有关的向上开口二次函数。

一张图像上的二次函数取最大值，发现还是一个单峰函数....

三分没了...

// Code by ajcxsu
// Problem: nature reserve

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
#define EPS (1e-7)
typedef long long ll;
using namespace std;

template<typename T> inline void gn (T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') pl=ch=='-', ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int N=1e5+10;
struct Node { int x, y; } nd[N];
int cnt[4];

int n;
double f(double x) {
    double ret=0, a, t;
    for(int i=1; i<=n; i++) {
        a=nd[i].y, t=fabs(nd[i].x-x);
        ret=max(ret, (a*a+t*t)/(2.0*a));
    }
    return ret;
}

int main() {
    gn(n);
    for(int i=1;i<=n;i++) {
        gn(nd[i].x), gn(nd[i].y);
        if(nd[i].y>0) cnt[0]++;
        else if(nd[i].y==0) cnt[1]++;
        else cnt[2]++;
        nd[i].y=abs(nd[i].y);
    }
    if(cnt[0] && cnt[2] || cnt[1]>2) puts("-1"), exit(0);
    double l=-1e7, r=1e7, m1, m2;
    while(r-l>EPS) {
        m1=(r-l)/3.0;
        m2=r-m1, m1+=l;
        if(f(m1)>f(m2)) l=m1;
        else r=m2;
    }
    printf("%.6lf\n", f(r));
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-cf-1059d.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆