牛牛战队的比赛地

题目链接:

https://ac.nowcoder.com/acm/contest/3006/F

题目描述:

题目大意:

给了n个点,求这n个点到X轴上的某一点的最大值的最小值。

解题思路:

最终的结果肯定在所给的点的X的最小值和X的最大值之间,也就是说最终选中的点(题目要求只能在X轴上,所以Y=0;)的X的范围在minX~maxX之间。通过作图可以发现,我们最终要求的那个赛点的位置在每种情况的最大值构成的一个开口向上的二次函数图像的最低点位置对应的(x,0)位置上。所以三分解决。

代码:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n;
struct node{
    int x,y;
    bool operator<(const node&t)const{
        if(x==t.x)return y<t.y;
        return x<t.x;
    }
};
node a[maxn];
double solve(int x,int y,double z){
    double len;
    len=(x-z)*(x-z)+y*y;
    len=sqrt(len);
    return len;
}
double check(double x){
    double ma;
    ma=-inf;
    for(int i=1;i<=n;i++){
        ma=max(solve(a[i].x,a[i].y,x),ma);
    }
    return ma;
}
 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    sort(a+1,a+n+1);
    double l,r;
    l=a[1].x;
    r=a[n].x;
    double f1,f2;
    while(r-l>1e-6){
        double mid1,mid2;
        mid1=(r-l)/3.0+l;
        mid2=r-(r-l)/3.0;
        f1=check(mid1);
        f2=check(mid2);
        if(f1>f2)l=mid1;
        else r=mid2;
    }
    printf("%f\n",f1);
    return 0;
}
Last modification:February 15th, 2020 at 10:02 am
如果觉得我的文章对你有用,请随意赞赏