牛客:牛牛战队的比赛地

这两天状态不行,先是lol排位赛连跪,又是昨晚cf掉分。唉。。。好不容易打上青名,又掉回去了。。。昨天晚上的cf必须让**出题人背个锅,B题出的什么玩意,发了第三篇公告我才读懂题意,导致C没时间做了,自己也要背锅,太菜了!今晚还有一场div.2。干就完了!

今天下午牛客也是!B题wa了八遍,知道用三分,用while写三分的出口总是超时!看了题解才知道for循环100次即可。还是当时没仔细去计算循环次数。

回到题目

原题链接:https://ac.nowcoder.com/acm/contest/3006/B

题意,给你n个点,在x轴上找一点,求出该点到所有点的最大距离的最小值。

在x轴,没法证明这些点是单调的,二分不好做,用三分来找峰值

一篇讲三分的博客:https://blog.csdn.net/wu_tongtong/article/details/79233657

代码:

 #include <bits/stdc++.h>
#define ll long long
using namespace std;
double ansm1=0,ansm2=0;
int n;
struct qq
{
    int x,y;
}q[100010];
void js(int m1,int m2)
{
    for(int i=0;i<n;i++)
    {
        ansm1=max(ansm1,sqrt((q[i].x-m1)*(q[i].x-m1)+q[i].y*q[i].y));
        ansm2=max(ansm2,sqrt((q[i].x-m2)*(q[i].x-m2)+q[i].y*q[i].y));
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {scanf("%d %d",&q[i].x,&q[i].y);}
    //sort(q,q+n,cmp);
    int l=-10000;
    int r=10000;
    double minn=99999999999;
    ansm1=-999999;ansm2=-999999;
    js(l,r);
    minn=min(minn,ansm1);
    minn=min(minn,ansm2);
    for(int i=0;i<100;i++)
    {
        int m1=(l+r)>>1;
        int m2=(m1+r)>>1;
        ansm1=-99999999;ansm2=-99999999;
        js(m1,m2);
        minn=min(minn,ansm1);
        minn=min(minn,ansm2);
        if(m1==l&&m2==r)
        {break;}
        if(ansm1>ansm2)
        {l=m1;}
        else
        {r=m2;}
    }
    cout<<minn<<endl;
    return 0;
}

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注