zju2282 -- challenge of bravery.cpp

来自「Zhejiang University Online Judge 第2277题至」· C++ 代码 · 共 53 行

// PROB         Zju Online Judge 2282 -- Challenge of Bravery
// Algorithm    SA
// Complexity   -
// Author       LoveShsean
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <stdlib.h>

#define maxn 50
#define sqr(x) ((x) * (x))

using namespace std;

double x [maxn], y [maxn], z [maxn], g [maxn] [maxn], cur, ans;
int n, id [maxn];

int main ()
{
 	srand ((unsigned) time (0));
 	int i, j, k, lp;
 	while (scanf ("%d", &n) == 1)
 	{
 	 	for (i = 0; i < n; i ++) scanf ("%lf%lf%lf", x + i, y + i, z + i);
 	 	for (i = 0; i < n; i ++)
 	 		for (j = 0; j < n; j ++)
 	 			g [i] [j] = sqrt (sqr (x [i] - x [j]) + sqr (y [i] - y [j]) + sqr (z [i] - z [j]));
 	 	ans = 1e30;
 	 	for (i = 0; i < n; i ++) id [i] = i;
 	 	for (k = 0; k < 10000; k ++)
 	 	{
 	 	 	random_shuffle (id + 1, id + n);
 	 	 	lp = 1; while (lp)
 	 	 	{
 	 	 	 	lp = 0;
 	 	 	 	for (i = 1; i < n; i ++)
 	 	 	 		for (j = i + 1; j < n - 1; j ++)
 	 	 	 			if (g [id [i - 1]] [id [i]] + g [id [j]] [id [j + 1]]
 	 	 	 			  > g [id [i - 1]] [id [j]] + g [id [i]] [id [j + 1]] + 1e-8)
 	 	 	 			  {
 	 	 	 			   	lp = 1;
 	 	 	 			   	reverse (id + i, id + j + 1);
 	 	 	 			  }
 	 	 	}
 	 	 	for (cur = 0, i = 0; i < n - 1; i ++)
 	 	 		cur += g [id [i]] [id [i + 1]];
 	 	 	if (cur < ans) ans = cur;
 	 	}
 	 	printf ("%.1lf\n", ans);
 	}
}