OJ Board

Code: Select all

/* CUT*/

#define delta(x,y) sqrt((rad[x]+rad[y])*(rad[x]+rad[y])-abs(rad[x]-rad[y])*abs(rad[x]-rad[y]))

/*CUT*/

Code: Select all

#define delta(x,y) 2*sqrt(rad[x]*rad[y])

Code: Select all

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

float circles[8];
float smallest;

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

float get_size_of_box(char *order, int N)
{	
	int poradi[8];
	for (int i = 0; i < 8; i++)
	{
		poradi[i] = order[i]-'0';
	}
	float partial_dist[8]; //stores distancies from the left side of the box up to the ith circle center   
	float centers[8]; 	//stores "coordinate" of the centers
	
	float size = 2*circles[poradi[0]];
	
	centers[0] = circles[poradi[0]];
	partial_dist[0] = circles[poradi[0]];
	float max_par_dist;
	float aux_dist;	
	
	for (int i  = 1; i < N; i++)
	{
		max_par_dist=0;
		for (int j = 0; j < i; j++)
		{
			aux_dist = 2*sqrt(circles[poradi[j]]*circles[poradi[i]]);
			if ((max_par_dist < (partial_dist[j]+aux_dist)) )
			{
				max_par_dist =  partial_dist[j]+aux_dist;
			}									//tim overime, ze se skutecne dotyka jen predposledniho
		}
		partial_dist[i] = max_par_dist;
		
		
		//ale muze nastat pripad, kdy je kulicka dosti mala
		if (partial_dist[i] < circles[poradi[i]])
			partial_dist[i] = circles[poradi[i]];
		if ((partial_dist[i]+circles[poradi[i]])> size)
			size = partial_dist[i]+circles[poradi[i]];
	}
	return size;
}

void permute(char *a, int i, int n)
{
	int j;
	if (i == n)
	{
		float size = get_size_of_box(a, n+1);
		if (size < smallest)
			smallest = size;
	}		
	else
	{
		for (j = i; j <= n; j++)
		{	
			swap((a+i), (a+j));
			permute(a, i+1, n);
			swap((a+i), (a+j)); //backtrack
		}
	}
} 

		
int main () 
{
	int cases;
	scanf("%d\n", &cases);
	char order[] = {'0', '1', '2', '3', '4', '5', '6', '7'};
	while (cases)
	{
		cases--;
		int N;
		scanf("%d", &N);
		for (int i = 0; i < N; i++)
			scanf(" %f", &circles[i]);
		getchar(); //end of line
		
		smallest = get_size_of_box(order, N);
		permute (order, 0, (N-1));
		
		printf("%.3f\n", smallest);
	}
	
} 

Code: Select all

middle at 0.306, radius 0.306
middle at 1.908, radius 1.908
middle at 5.048, radius 1.292
middle at 8.710, radius 2.595
middle at 11.119, radius 0.559
maxright = 11.678

middle at 0.306, radius 0.306
middle at 1.908, radius 1.908
middle at 3.973, radius 0.559
middle at 6.382, radius 2.595
middle at 10.044, radius 1.292
maxright = 11.336

middle at 1.908, radius 1.908
middle at 3.973, radius 0.559
middle at 6.382, radius 2.595
middle at 8.165, radius 0.306
middle at 10.044, radius 1.292
maxright = 11.336