#include <stdio.h>
#include <math.h>

#define INF 0xffffffff
#define MAX_N 205

typedef struct { int x, y; } postype;

int cmp(const void *prev, const void *next)
{
  return ((postype *)prev)->x > ((postype *)next)->x ? 1 : -1;
}

double euclid_dist(postype a, postype b)
{
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main()
{
  int n;
  postype p[MAX_N];
  int i, j;
  double f[MAX_N][MAX_N];
  

  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  
  while (scanf("%d", &n) > 0)
  {
	  for (i = 1; i <= n; i++)
	    scanf("%d%d", &p[i].x, &p[i].y);
	  qsort(p + 1, n, sizeof(postype), cmp);
	  
	  f[1][2] = euclid_dist(p[1], p[2]);
	  for(j = 3; j <= n; j++)
	  {
	    for (i = 1; i < j - 1; i++)
	      f[i][j] = f[i][j - 1] + euclid_dist(p[j - 1], p[j]);
	    
	    f[j - 1][j] = INF;
	    for (i = 1; i < j - 1; i++)
	    {
	      double temp = f[i][j - 1] + euclid_dist(p[i], p[j]);
	      if (temp < f[j - 1][j])
	        f[j - 1][j] = temp;
	    }
	  }
	  
	  printf("%.2lf\n", f[n - 1][n] + euclid_dist(p[n - 1], p[n]));
  }
  
  //fclose(stdin);
  //fclose(stdout);
  
  return 0;
}

• Re:为啥Language选C就AC，选GCC就WA呢？ (1351) lok41 2012-11-17 16:45:19