QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#678761 | #5667. Meeting Places | Forever_Young# | WA | 1ms | 3884kb | C++14 | 2.3kb | 2024-10-26 16:04:23 | 2024-10-26 16:04:23 |
Judging History
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));
}
详细
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'