社区讨论
爬山为什wa啊
UVA10228A Star not a Tree?参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi7dcg0n
- 此快照首次捕获于
- 2025/11/20 19:49 4 个月前
- 此快照最后确认于
- 2025/11/20 19:49 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,t;
double sx,sy,xx[1001],yy[1001];
const int px[]={0,0,-1,1};
const int py[]={-1,1,0,0};
const double eps=1e-5;
double calc(double x,double y){
double ret=0;
for(int i=1;i<=n;i++){
ret+=sqrt((xx[i]-x)*(xx[i]-x)+(yy[i]-y)*(yy[i]-y));
}
return ret;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
sx=0,sy=0;
for(int i=1;i<=n;i++){
scanf("%lf%lf",&xx[i],&yy[i]);
sx+=xx[i];
sy+=yy[i];
}
sx/=n;sy/=n;
double ans=calc(sx,sy),delta=1e4;
while(delta>eps){
for(int i=0;i<4;i++){
double tmp=calc(sx+px[i]*delta,sy+py[i]*delta);
if(tmp<ans){
ans=tmp;
sx=sx+px[i];
sy=sy+py[i];
}
}
delta*=0.9;
}
printf("%.0lf\n",ans);
if(t)puts("");
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...