OJ Board

Code: Select all

8
A 886 383
B 915 777
C 335 793
D 492 386
E 421 649
F 27 362
G 59 690
H 926 763
I 426 540
J 736 172
K 368 211
L 429 567
M 530 782
N 123 862
O 135 67
P 802 929
8
A 58 22
B 167 69
C 456 393
D 42 11
E 373 229
F 919 421
G 537 784
H 324 198
I 370 315
J 526 413
K 980 91
L 873 956
M 170 862
N 281 996
O 925 305
P 327 84
8
A 505 336
B 729 846
C 857 313
D 895 124
E 545 582
F 367 814
G 364 434
H 750 43
I 808 87
J 178 276
K 584 788
L 651 403
M 399 754
N 60 932
O 368 676
P 12 739
8
A 586 226
B 539 94
C 570 795
D 378 434
E 601 467
F 902 97
G 492 317
H 756 652
I 280 301
J 441 286
K 689 865
L 619 444
M 729 440
N 117 31
O 771 97
P 675 481
8
A 927 709
B 856 567
C 353 497
D 965 586
E 683 306
F 624 219
G 871 528
H 829 732
I 19 503
J 368 270
K 715 708
L 149 340
M 723 796
N 245 618
O 451 846
P 555 921
0

Code: Select all

Case 1: 1492.91
Case 2: 1519.71
Case 3: 1293.73
Case 4: 1290.51
Case 5: 1344.81

Code: Select all

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

#define MAX 16
#define LEN 25

struct punt
{
	int x, y;
};

struct pepe
{
	int num;
	double dis;
};

int k, i, j, n;
int mark[MAX], testNum;
struct punt punt1[MAX];
struct pepe matr1[MAX][MAX];
double m;

void Avanza(int, double);

int sort(const void *a, const void *b)
{
	struct pepe *aa = (struct pepe*)a;
	struct pepe *bb = (struct pepe*)b;
		
	return (aa->dis <= bb->dis) ? -1 : 1;
}

void BuscaPareja(int aQuien, int parejas, double dist)
{
	int a, b;
	double c;
	
	if (m != -1.0 && dist >= m)
		return;
	
	for (a = 0; a < 2 * n; a++)
	{
		if (m != -1.0 && dist >= m)
			return;
	
		b = matr1[aQuien][a].num;
		
		if (!mark[b])
		{
			c = matr1[aQuien][a].dis;
			mark[b] = 1;
			
			if (parejas + 1 < n && (m == -1 || m > dist + c))
				Avanza(parejas + 1, dist + c);
			else
			{
				if (m == -1.0 || dist + c < m)
					m = dist + c;
			}
			
			mark[b] = 0;
		}
	}
}

void Avanza(int parejas, double dist)
{
	int a;
	
	for (a = 0; a < 2 * n; a++)
	{
		if (m != -1.0 && dist >= m)
			return;
		
		if (!mark[a])
		{
			mark[a] = 1;
			BuscaPareja(a, parejas, dist);
			mark[a] = 0;
		}
	}
}

int main()
{
	char cad[LEN];
	
	scanf("%d", &n);
	testNum = 0;
	
	while (n)
	{
		for (k = 0; k < 2 * n; k++)
			scanf("%s %d %d", &cad, &punt1[k].x, &punt1[k].y);
		
		for (i = 0; i < 2 * n; i++)
			for (j = i; j < 2 * n; j++)
			{
				matr1[i][j].num = j;
				matr1[i][j].dis = sqrt(
				(punt1[i].x - punt1[j].x) * (punt1[i].x - punt1[j].x) 
						+ 
				(punt1[i].y - punt1[j].y) * (punt1[i].y - punt1[j].y));
				
				matr1[j][i].num = i;
				matr1[j][i].dis = matr1[i][j].dis;
			}
			
		for (k = 0; k < 2 * n; k++)
		{
			qsort(matr1[k], 2 * n, sizeof(struct pepe), sort);
			mark[k] = 0;
		}
				
		m = -1.0;
		Avanza(0, 0.0);
		
		//puts("...");
		
		printf("Case %d: %0.2lf\n", ++testNum, m);
		scanf("%d", &n);	
	}
	
	return 0;
}

Code: Select all

               (1,2)
   --------------+--------------
  /     /     /     \     \     \
(3,4) (3,5) (3,6) (4,5) (4,6) (5,6)
  |     |     |     |     |     |
(5,6) (4,6) (4,5) (3,6) (3,5) (3,4)


               (3,4)
   --------------+--------------
  /     /     /     \     \     \
(1,2) (1,5) (1,6) (2,5) (2,6) (5,6)
  |     |     |     |     |     |
(5,6) (2,6) (2,5) (1,6) (1,5) (1,2)


               (5,6)
   --------------+--------------
  /     /     /     \     \     \
(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)
  |     |     |     |     |     |
(3,4) (2,4) (2,3) (1,4) (1,3) (1,2)