2014083 2006-08-10 20:56:11 Accepted 1901 C++ 00:00.06 516K St.Crux 这个题如果用穷举则超时：总共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;}

评论