题解

嘛。。。

发一下自己的写法

虽然比赛时各种爆炸,被卡精度卡时间卡到40pts

第一眼看上去题目

woc这不是三分套三分傻逼题吗(虽然比赛后好像就我一个写的三分套三分

然后写一发交了上去

[qwq](https://www.luogu.org/recordnew/show/17080152)

这个eps写的1e-3

然后各种调参

把eps改成1e-6

就可以调到30分了

30pts代码↓(比赛时

#include <bits/stdc++.h>
#define il inline
#define Max 100005
#define db long double
#define inf 1e16
using namespace std;
int n;
db eps=1e-6;
struct node
{
    db x,y,r;
}p[Max],S[Max];
db ansx,ansy,ansr,maxx,maxy,minx,miny;
il db dis(int i,db xx,db yy)
{
    return sqrt((p[i].x-xx)*(p[i].x-xx)+(p[i].y-yy)*(p[i].y-yy));
}
il db calc2(db xx,db yy)
{
    db res=0;
    for(int i=1;i<=n;i++) res=max(res,dis(i,xx,yy)+p[i].r);
    ansr=res;
    return res;
}
il db calc(db xx)
{
    db l=miny,r=maxy;
    while(r-l>=eps)
    {
        db k=(r-l)/3.0;
        db mid1=l+k,mid2=r-k;
        if(calc2(xx,mid1)<calc2(xx,mid2)) r=mid2;
        else l=mid1;
    }
    ansy=l;
    return calc2(xx,ansy);
}
il bool cmp(node a,node b)
{
    db A=atan2((a.y-p[1].y),(a.x-p[1].x));
    db B=atan2((b.y-p[1].y),(b.x-p[1].x));
    if(A!=B) return A<B;
    else return a.x<b.x;
}
il db cross(node a,node b,node c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void Get()
{
    p[0]=(node){inf,inf};
    int k=1,top;
    for(int i=1;i<=n;++i)
        if(p[0].y>p[i].y||(p[0].y==p[i].y&&p[i].x<p[0].x))
            p[0]=p[i],k=i;
    swap(p[k],p[1]);
    sort(&p[2],&p[n+1],cmp);
    S[0]=p[1],S[1]=p[2];top=1;
    for(int i=3;i<=n;)
    {
        if(top&&cross(S[top-1],p[i],S[top])>=0)
            top--;
        else S[++top]=p[i++];
    }
    for(int i=0;i<=top;i++)
        p[i]=S[i];
    n=top;
}
int main()
{
    scanf("%d",&n);
    if(n<100) eps=1e-7;
    minx=miny=10100;
    maxx=maxy=-10100;
    for(int i=1;i<=n;i++)
        scanf("%Lf%Lf%Lf",&p[i].x,&p[i].y,&p[i].r),maxx=max(p[i].x+p[i].r,maxx),minx=min(minx,p[i].x-p[i].r),maxy=max(maxy,p[i].y+p[i].r),miny=min(miny,p[i].y-p[i].r);
    //Get();
    db l=minx,r=maxx;
    while(r-l>=eps)
    {
        db k=(r-l)/3.0;
        db mid1=l+k,mid2=r-k;
        if(calc(mid1)<calc(mid2)) r=mid2;
        else l=mid1;
    }
    calc(l);
    ansx=l;
    printf("%.3Lf %.3Lf %.3Lf\n",ansx,ansy,ansr);
}

被毒瘤#1卡精度怎么改都过不去

评测记录

qwq2

我们考虑第5个点,r=0。

发现只要求一个凸包就可以了。

里面的点就不用管了。

然后比赛时候开心的写了一发凸包。

拿了40pts。

40分代码↓

#include <bits/stdc++.h>
#define il inline
#define Max 100005
#define db long double
#define inf 1e16
using namespace std;
int n,st;
db eps=1e-6;
struct node
{
    db x,y,r;
}p[Max],S[Max];
bool flag=1;
db ansx,ansy,ansr,maxx,maxy,minx,miny;
il db dis(int i,db xx,db yy)
{
    return sqrt((p[i].x-xx)*(p[i].x-xx)+(p[i].y-yy)*(p[i].y-yy));
}
il db calc2(db xx,db yy)
{
    db res=0;
    for(int i=1;i<=n;i++) res=max(res,dis(i,xx,yy)+p[i].r);
    ansr=res;
    return res;
}
il db calc(db xx)
{
    db l=miny,r=maxy;
    while(r-l>=eps)
    {
        db k=(r-l)/3.0;
        db mid1=l+k,mid2=r-k;
        if(calc2(xx,mid1)<calc2(xx,mid2)) r=mid2;
        else l=mid1;
    }
    ansy=(l+r)/2.0;
    return calc2(xx,ansy);
}
il bool cmp(node a,node b)
{
    db A=atan2((a.y-p[1].y),(a.x-p[1].x));
    db B=atan2((b.y-p[1].y),(b.x-p[1].x));
    if(A!=B) return A<B;
    else return a.x<b.x;
}
il db cross(node a,node b,node c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void Get()
{
    p[0]=(node){inf,inf};
    int k=1,top;
    for(int i=1;i<=n;++i)
        if(p[0].y>p[i].y||(p[0].y==p[i].y&&p[i].x<p[0].x))
            p[0]=p[i],k=i;
    swap(p[k],p[1]);
    sort(&p[2],&p[n+1],cmp);
    S[0]=p[1],S[1]=p[2];top=1;
    for(int i=3;i<=n;)
    {
        if(top&&cross(S[top-1],p[i],S[top])>=0)
            top--;
        else S[++top]=p[i++];
    }
    for(int i=0;i<=top;i++)
        p[i]=S[i];
    n=top;
}
int main()
{
    scanf("%d",&n);
    st=clock();
    minx=miny=10100;
    maxx=maxy=-10100;
    if(n<=100) eps=1e-7;
    if(n>1000) eps=1e-5;
    for(int i=1;i<=n;i++)
        scanf("%Lf%Lf%Lf",&p[i].x,&p[i].y,&p[i].r),maxx=max(p[i].x+p[i].r,maxx),minx=min(minx,p[i].x-p[i].r),maxy=max(maxy,p[i].y+p[i].r),miny=min(miny,p[i].y-p[i].r),flag=(p[i].r==0);
    if(flag) Get();
    db l=minx,r=maxx;
    while(r-l>=eps)
    {
        if(clock()-st>3630000) break;
        db k=(r-l)/3.0;
        db mid1=l+k,mid2=r-k;
        if(calc(mid1)<calc(mid2)) r=mid2;
        else l=mid1;
    }
    calc((l+r)/2.0);
    ansx=(l+r)/2.0;
    if(fabs(ansx)<1e-2) ansx=fabs(ansx);
    if(fabs(ansy)<1e-2) ansy=fabs(ansy);
    if(fabs(ansr)<1e-2) ansr=fabs(ansr);
    printf("%.3Lf %.3Lf %.3Lf\n",ansx,ansy,ansr);
}

这份代码考试时被毒瘤的出题人卡精度卡空间。

考试后数据精度改了就可以过了。

顺便附上赛时的评测记录和赛后的评测记录

赛时 赛后

闲聊

其实考试时想到了可以求一个圆的凸包。

这样说不定就可以过了。

但是圆的凸包太麻烦了,于是就没有写。

有兴趣的可以写写,去网上查查就好了。

还有这题也可以用模拟退火的说。

但是由于我太菜,模拟退火的题写的少,所以没写。

还有正解的思路好强啊,根本没想到可以那样做。

圆的最小覆盖的模板我怎么听都没听过

还有初中基础数学是什么鬼,我怎么都不会证明

总体来说这题拿来练三分也挺好的(雾

对了这题#5不求凸包的话会T掉(如果你能卡过去也行

最后建议各位学习下正解,至少那个效率可以吊打这个代码