WA求助
查看原帖
WA求助
1047309
return_second楼主2024/1/21 15:31
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
int n,maxx=-1e9,maxy=-1e9,minx=1e9,miny=1e9;
double minn=1e9,num=0;
const int f[][2]={{-1,0},{1,0},{0,-1},{0,1}};//上、下、左、右 
struct stu
{
	int x,y;
}a[20];
double dis(int x1,int y1,int x2,int y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void dfs(int x,int y,int sum=n)
{
	if(x<minx||x>maxx||y<miny||y>maxy)
		return;
	for(int i=1;i<=n;i++)
		if(a[i].x==x&&a[i].y==x)
		{
			sum--;
			break;
		}
	if(sum==0)
	{
		minn=min(minn,num);
		num=0.00;
		return;
	}
	for(int i=0;i<4;i++)
	{
		num+=dis(x,y,x+f[i][0],y+f[i][1]);
		dfs(x+f[i][0],y+f[i][1],sum);
		num-=dis(x,y,x+f[i][0],y+f[i][1]);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		maxx=max(maxx,a[i].x);
		maxy=max(maxy,a[i].y);
		minx=min(minx,a[i].x);
		miny=min(miny,a[i].y);
	}
	dfs(0,0);
	printf("%.2lf",minn);
	return 0;
}
2024/1/21 15:31
加载中...