QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#678761#5667. Meeting PlacesForever_Young#WA 1ms3884kbC++142.3kb2024-10-26 16:04:232024-10-26 16:04:23

Judging History

你现在查看的是最新测评结果

  • [2024-10-26 16:04:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3884kb
  • [2024-10-26 16:04:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
double R,eps=1e-10;
struct P{double x,y;}a[2005],O;
double dis(P x,P y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
int K0,K1,K2;
P center(P x,P y,P z)
{
    double a1=y.x-x.x,b1=y.y-x.y,
            c1=(a1*a1+b1*b1)/2,a2=z.x-x.x,
            b2=z.y-x.y,c2=(a2*a2+b2*b2)/2,
            d=a1*b2-a2*b1;
    return (P){x.x+(c1*b2-c2*b1)/d,x.y+(a1*c2-a2*c1)/d};
}
double cal(int n,P *b){
    K0=0,K1=K2=-1;
    int i,j,k;
    for(i=0;i<n;i++)a[i]=b[i];
    for(i=0;i<n;i++)swap(a[rand()%n],a[i]);
    for(O=a[0],R=0,i=1;i<n;i++)if(dis(a[i],O)>R+eps)
            for(O=a[i],R=0,j=0;j<i;++j)if(dis(a[j],O)>R+eps){
                    O=(P){(a[i].x+a[j].x)/2,(a[i].y+a[j].y)/2},R=dis(O,a[i]),K0=i,K1=j,K2=-1;
                    for(k=0;k<j;k++)if(dis(a[k],O)>R+eps)O=center(a[k],a[j],a[i]),R=dis(O,a[i]),K0=i,K1=j,K2=k;
                }
    return R;
}
P dot[2005];
int n,k;

long long x[2005],y[2005];
long long nxt(long long x){
    return (x*233811181+1)%((1ll<<31)-1);
}

int main(){
    scanf("%d%d%lld",&n,&k,&x[1]);
    y[1]=nxt(x[1]);
    for (int i=2;i<=n;i++) {
        x[i] = nxt(y[i - 1]);
        y[i] = nxt(x[i]);
    }
    for (int i=0;i<n;i++) dot[i]={x[i+1],y[i+1]};

//    printf("%.10f\n",cal(n,dot));
    while(n>1&&k>1){
        double r=cal(n,dot);
        double r0=r,r1=r,r2=r;
        int KK0=K0,KK1=K1,KK2=K2;
        swap(dot[KK0],dot[n-1]);
        r0=cal(n-1,dot);
        swap(dot[KK0],dot[n-1]);
        swap(dot[KK1],dot[n-1]);
        r1=cal(n-1,dot);
        swap(dot[KK1],dot[n-1]);
        if (K2>=0) {
            swap(dot[KK2], dot[n - 1]);
            r2 = cal(n - 1, dot);
            swap(dot[KK2], dot[n - 1]);
        }
//        printf("%d %d %d %lf\n",K0,K1,K2,dis(dot[K0],center(dot[K0],dot[K1],dot[K2])));
//        printf("%lf %lf %lf\n",r0,r1,r2);
        if (r0<=r1&&r0<=r2){
//            printf("%d\n",K0);
            swap(dot[KK0],dot[n-1]);
        } else if(r1<=r0&&r1<=r2){
//            printf("%d\n",K1);
            swap(dot[KK1],dot[n-1]);
        } else{
            swap(dot[KK2],dot[n-1]);
//            printf("%d\n",K2);
        }
        n--,k--;
    }
//    20928343844.1572303772
//     1319350480.8007326126
    printf("%.10f\n",cal(n,dot));
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3884kb

input:

100 23 213

output:

1299388001.2863538265

result:

wrong answer 1st numbers differ - expected: '1319350480.8007326', found: '1299388001.2863538', error = '0.0151305'