社区讨论

爬山为什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 条回复,欢迎继续交流。

正在加载回复...