这个题如果用穷举则超时：总共10000*10000个点。因此考虑从中心点出发向四周扩散搜索。这还是上个学期做的题，一直wronganswer。

#include <cstdio>
#include <cmath>

int xi[100], yi[100];
int dir[8][2] = {{-1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 0}, {0, -1}, {1, -1}, {-1, 1}};
double min;
int n;

void dfs(int x, int y)
{
 int i, k;
 double tm = 0;
 for(i = 0; i < n; i ++)
 {
  tm += sqrt((x - xi[i]) * (x - xi[i]) + (y - yi[i]) * (y - yi[i]));
 }
 if(tm < min)
 {
  min = tm;
  for(k = 0; k < 8; k ++)
  {
   int xx = x + dir[k][0];
   int yy = y + dir[k][1];
   dfs(xx, yy);
  }
 }
 else
  return;
}
 

int main()
{
 int i;
 //freopen("in.txt", "r", stdin);
 while(scanf("%d", &n) != EOF)
 {
  int x0 = 10000, x1 = 0, y0 = 10000, y1 = 0;
  for(i = 0; i < n; i ++)
  {
   scanf("%d%d", &xi[i], &yi[i]);
   if(xi[i] < x0) x0 = xi[i];
   if(yi[i] < y0) y0 = yi[i];
   if(xi[i] > x1) x1 = xi[i];
   if(yi[i] > y1) y1 = yi[i];
  }
  int x = (x0 + x1) / 2, y = (y0 + y1) / 2;
  min = 99999999;
  dfs(x, y);
  
  //printf("%0.3f ", min);
  int m = int(min);  
  if(min - m >= 0.50)
   m ++;
  printf("%d\n", m);
 }
 return 0;
}

评论