OJ Board

Code: Select all

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#define MAXNODES 8
using namespace std;
class Node
{
public:
    double x,y;
    Node(){}
    Node(double i,double j){x = i ; y = j;}
    double getDist(Node a){return sqrt((x-a.x)*(x-a.x)+(y-a.y)*(y-a.y));}
};
class Wire
{
public:
    int i,j;
    double size;
    Wire(){}
    Wire(int I,int J,Node a,Node b){i = I ; j = J ; size = a.getDist(b)+16;}
};

Node N[MAXNODES];
Wire W[MAXNODES-1];
bool used[MAXNODES];
Wire best[MAXNODES-1];
double bestSize;
void solve(int index , int fav , double length , int last)
{
    if(index == fav)
    {
        if(length < bestSize || bestSize == -1)
        {
            bestSize = length;
            copy(W,W+fav,best);
        }
        return ;
    }
    for(int i=0;i<fav;i++)
    {
        if(!used[i])
        {
            used[i] = 1;

            if(index > 0)
            {
                W[index-1]=Wire(last,i,N[last],N[i]); 
                solve(index+1,fav,length+W[index-1].size,i);
            }
            else
                 solve(index+1,fav,length,i);

            used[i] = 0;
        }
    }
}
int main()
{
    int n,m,k,t;
    t = 0;
    cin >> n;
    while(n)
    {
        for(int i=0;i<n;i++)
            cin >> N[i].x >> N[i].y;
        memset(used,0,sizeof(used));
        bestSize = -1;
        solve(0,n,0,0);
        cout << "**********************************************************"<<endl;
        cout <<"Network #"<<++t<< endl;
        for(int i=0;i<n-1;i++)
        {
           cout << "Cable requirement to connect (" << N[best[i].i].x << "," << N[best[i].i].y << ") to (" << N[best[i].j].x << "," << N[best[i].j].y << ") is ";
           printf("%3.2lf",best[i].size);
           cout <<" feet."<<endl;
        }
        printf("Number of feet of cable required is %3.2lf.\n",bestSize);
        cin >> n;
    }
	return 0;
}

Code: Select all

CODE DELETED AFTER AC :)

   

Code: Select all

GOT AC

Code: Select all

double d(int x1, int y1, int x2, int y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

Code: Select all

double d(int x1, int y1, int x2, int y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))+16;
}

Code: Select all

//216.getting in line (brute force)
//determine how the computers should be connected into such a chain to minimize the total amount of cable needed
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define X 0
#define Y 1
using namespace std;

int pts[8][2];
int index[]={0,1,2,3,4,5,6,7};
int target[8];
double dist(int a[],int b[]){
    return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y])+16.0);
}
main(){
    int n,i,casos=0;
    double minimo,dist_total;
    while (scanf ("%d\n",&n) && n){
        for (i=0; i<n; i++)
            scanf ("%d %d\n",&pts[i][X],&pts[i][Y]);
        minimo=99999999;
        
        do{
            dist_total=0;
            for (i=0; i<n-1; i++)
                dist_total+= dist(pts[index[i]],pts[index[i+1]]);
                
            if (dist_total < minimo){
                minimo = dist_total;//guarda el orden
                memcpy(target,index,sizeof(index));
            }
        }while (next_permutation(index,index+n));
        printf ("**********************************************************\nNetwork #%d\n",++casos);
        for (int i=0; i<n-1; i++){
            printf ("Cable requirement to connect (%d,%d) to (%d,%d) is %3.2lf feet.\n",
            pts[target[i]][X],pts[target[i]][Y],pts[target[i+1]][X],pts[target[i+1]][Y],
            dist(pts[target[i]],pts[target[i+1]]));
        }
        printf ("Number of feet of cable required is %3.2lf.\n",minimo);
    }
}

Code: Select all

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

int main()
{
	int perm[] = {1,2,3,4,5,6,7,8};
	int count;
	int bestperm[8];
	int computers[2][8];
	double smallest = 0.0;
	double current = 0.0;
	double x, y;
	int network = 1;
	double chunk, total;
	
	cin >> count;
	
	while(count != 0)
	{
		current = 0.0;
		smallest = 0.0;
		total = 0.0;
		chunk = 0.0;
		
		for (int i = 0; i < count; i++)
		{
			cin >> computers[0][i] >> computers[1][i];
		}
		
		
		sort(perm, perm+count);     // gives the smallest permutation
		do {
			current = 0.0;
						
			for(int i = 0; i < count - 1; i++)
			{
				
				x = computers[0][perm[i]-1] - computers[0][perm[i+1]-1];
				y = computers[1][perm[i]-1] - computers[1][perm[i+1]-1];
				
				current += sqrt(x*x + y*y);								
			}
					
			if ((current < smallest) || (smallest == 0.0))
			{
				
				smallest = current;
				for (int i = 0; i < count; i++)
				{
					bestperm[i] = perm[i];
				}
			}
			
		} while (next_permutation(perm, perm+count));
		
	
		cout << "**********************************************************\n"
			<< "Network #" << network << "\n";
		for (int i = 0; i < count - 1; i++)
		{
			cout << "Cable requirement to connect (" 
				 << computers[0][bestperm[i]-1] << "," << computers[1][bestperm[i]-1] << ") to ("
				 << computers[0][bestperm[i+1]-1]<< "," << computers[1][bestperm[i+1]-1] << ") is ";
			x = computers[0][bestperm[i]-1] - computers[0][bestperm[i+1]-1];
			y = computers[1][bestperm[i]-1] - computers[1][bestperm[i+1]-1];
			chunk = sqrt(x*x + y*y) + 16;
			total += chunk;
			cout.setf(ios::fixed);
			cout << setprecision(2) <<  chunk << " feet.\n";					 
					 
		}
		
		cout << "Number of feet of cable required is " << setprecision(2) << total << endl;
		network++;
		
		cin >> count;
	}

	return 0;
}