216 - Getting in Line

[Robert Gerbicz]

Actually, I have the same output for the samples posted.

I don't think that.
For example this line is wrong:

Code: Select all

return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y])+16.0);

because the cabel is longer by 16 feets than the distance of the two points, so it should be:

Code: Select all

return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y]))+16.0;

There can be some other errors also.
And your program is little ugly, I would never write this:

Code: Select all

#define X 0
#define Y 1 

[zid_adrenalyns]

Actually, I have the same output for the samples posted.

I don't think that.
For example this line is wrong:

Code: Select all

return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y])+16.0);

because the cabel is longer by 16 feets than the distance of the two points, so it should be:

Code: Select all

return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y]))+16.0;

U r right!, I made a terrible mistake, but I have fixed that in my last submition (before the last post).

And your program is little ugly, I would never write this:

Code: Select all

#define X 0
#define Y 1 

About the code post below, U can chage this lines for enum{X,Y}; I think this is irrelevant.

There can be some other errors also.

Are u find them? Please tell me.

[gba356]

I tried to solve the problem with DFS and some branch and bound, but it keeps give me WA.

Could somebody help me?

Code: Select all

#include<iostream>
#include<math.h>
#define N 10
#define INF 214748647
#define Dist(i,j) sqrt( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) )
using namespace std;

int n,x[N],y[N];
int visit[N]={0},path[N],minpath[N];
double mindist,dist[N][N];

inline void
DFS(int start,int depth,double tempdist)
{
    path[depth-1]=start;               
    if( tempdist>=mindist )return;     
    if( depth==n&&tempdist<mindist )                     
    {
        for(int i=0;i<n;i++)
            minpath[i]=path[i];        
        mindist=tempdist;             
        return;
    }
    for(int i=0;i<n;i++)  /* DFS */
        if( !visit[i] )
        {
            visit[i]=1;
            DFS(i,depth+1,tempdist+dist[start][i]);
            visit[i]=0;
        }
}

int main()
{
//    freopen("216.in","r",stdin);
//    freopen("216.out","w",stdout);
    cout.setf(ios::fixed); 
    cout.precision(2);
    int case_n=0;
    while( cin>>n,n )     
    {
        mindist=INF;       
        for(int i=0;i<n;i++)
            cin>>x[i]>>y[i];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                dist[i][j]=dist[j][i]=Dist(i,j);
        for(int i=0;i<n;i++)
            DFS(i,0,0);
        cout<<"**********************************************************"<<endl;
        cout<<"Network #"<<++case_n<<endl;
        
        for(int i=0;i<n-1;i++)
            cout<<"Cable requirement to connect ("<<x[minpath[i]]<<","
                <<y[minpath[i]]<<") to ("<<x[minpath[i+1]]<<","<<y[minpath[i+1]]<<") is "
                <<dist[minpath[i]][minpath[i+1]]+16<<" feet."<<endl;
        cout<<"Number of feet of cable required is "<<mindist+16*(n-1)<<"."<<endl;
    }
}

[ahmadfarid]

please help please please please
i tried all the sample I/O but still getting wrong answer. :'(

[/code]#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;

//ifstream in ("input.txt");
//ofstream out ("output.txt");

long n;
long path[10];
bool valid[10];
long x[8], y[8];
double minimum = 2147483647;
double total = 0;
long order[8];
long X[8], Y[8];
double Dis[8];

void Display()
{
long i;
total = 0;
for(i=0; i<n-1; i++)
{
// out << path << " ";
double xdif, ydif;
xdif = x[path[i+1]] - x[path];
ydif = y[path[i+1]] - y[path];

total += (16+sqrt(pow(double(ydif),2.0)+pow(double(xdif),2.0)));

}

// out << "\t" << total << endl;
if(minimum>total)
{
minimum = total;
for(i=0; i<n; i++)
{
double xdif = x[path[i+1]] - x[path];
double ydif = y[path[i+1]] - y[path];
X = x[path];
Y = y[path];
Dis = (16+sqrt(pow(double(ydif),2.0)+pow(double(xdif),2.0)));
}

}

}

void Permutation(long counter)
{
if(counter == n)
{
total = 0;
Display();
return;
}
long i;
for(i=0; i<n; i++)
{
if(valid[i])
{
valid[i] = false;
path[counter] = i;
Permutation(counter+1);
valid[i] = true;
}
}
}

int main()
{
long counterr = 0;

while (cin >> n)
{
if (n==0)
break;




for (long i=0; i<n; i++)
cin >> x[i] >> y[i];

for(long i=0; i<n; i++)
valid[i] = true;

Permutation(0);
Display();

//if (counterr!=0)
cout<<"**********************************************************"<<endl;
cout << "Network #" << ++counterr << endl;


for (long i=0; i<n-1; i++)
{
double xdif = X[i] - X[i+1];
double ydif = Y[i] - Y[i+1];
cout << "Cable requirement to connect (" << X[i] << "," << Y[i] << ") to (" << X[i+1] << "," << Y[i+1] << ") is ";
cout << setiosflags(ios::fixed) << setiosflags(ios::showpoint) << setprecision(2) << Dis[i] << " feet.\n";
}
cout << "Number of feet of cable required is ";
cout << setiosflags(ios::fixed) << setiosflags(ios::showpoint) << setprecision(2) << minimum << "." << endl;

minimum = 2147483647;
total = 0;



}
return 0;
}

[Orgi]

Can anybody supply some test cases for 216?
Please, if someone has AC on C or C++, i'd like to know how he/she copes with rounding errors?

[haaaz]

I am also getting WA on the new server when I tried to resubmit codes I wrote long time ago... I have tried all sample inputs I found in this forum and I think my program gives the correct outputs.

I am just using DFS brute force....

AND most importantly my code got accepted a few years ago on the old server!!! can anybody help?

Code: Select all

//p216 Getting in Line

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

const double INF=999999999999.0;
struct com {
    int x,y;
};
com comlist[8];    
int n;
int list[8],ans[8];
double total;
double d[8][8];
bool used[8]={false};
double dist(com a, com b) {
    return sqrt(double(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))+16;
}    

void p(int depth) {
    if (depth==n) {
        //caluculate distance
        double t=0;
        for (int i=1; i<n; i++) t+= d[ list[i-1] ][ list[i] ];
        if (t<total) {
            total=t;
            for (int i=0; i<n; i++) ans[i]=list[i];
        }    
        return;
    }
    for (int i=0; i<n; i++) {
        if (used[i]) continue;
        list[depth]=i;
        used[i]=true;
        p(depth+1);
        used[i]=false;
    }    
}

int main() {
    com x;    
    int test=1;
    cout.setf(ios::fixed);
    cout.precision(2);
    while (cin >> n) {
        if (n==0) break;
        total=INF;
        cout << "**********************************************************\n"
             << "Network #" << test << '\n';
   
        for (int i=0; i<n; i++) {
            list[i]=i;
            cin >> x.x >> x.y;
            comlist[i]=x;
        }
        for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) d[i][j]=dist(comlist[i],comlist[j]);
        p(0);
        for (int i=1; i<n; i++) {
            cout << "Cable requirement to connect (" << comlist[ans[i-1]].x << "," << comlist[ans[i-1]].y
                 << ") to (" << comlist[ans[i]].x << "," << comlist[ans[i]].y << ") is " << d[ans[i-1]][ans[i]] << " feet.\n";
        }    
        cout << "Number of feet of cable required is " << total << ".\n";
        test++; 
    }
    return 0;
}        

[/code]

[Shafaet_du]

Try this cases:

Code: Select all

8
100 150
102 23
34 67
32 63
11 25
132 35
54 122
54 23
8
120 15
102 21
34 64
132 16
1 125
13 135
12 162
55 45
0

output:

Code: Select all

**********************************************************
Network #1
Cable requirement to connect (132,35) to (102,23) is 48.31 feet.
Cable requirement to connect (102,23) to (54,23) is 64.00 feet.
Cable requirement to connect (54,23) to (11,25) is 59.05 feet.
Cable requirement to connect (11,25) to (32,63) is 59.42 feet.
Cable requirement to connect (32,63) to (34,67) is 20.47 feet.
Cable requirement to connect (34,67) to (54,122) is 74.52 feet.
Cable requirement to connect (54,122) to (100,150) is 69.85 feet.
Number of feet of cable required is 395.62.
**********************************************************
Network #2
Cable requirement to connect (132,16) to (120,15) is 28.04 feet.
Cable requirement to connect (120,15) to (102,21) is 34.97 feet.
Cable requirement to connect (102,21) to (55,45) is 68.77 feet.
Cable requirement to connect (55,45) to (34,64) is 44.32 feet.
Cable requirement to connect (34,64) to (1,125) is 85.35 feet.
Cable requirement to connect (1,125) to (13,135) is 31.62 feet.
Cable requirement to connect (13,135) to (12,162) is 43.02 feet.
Number of feet of cable required is 336.10.

no need to use eps

[@li_kuet]

I have tried all the test case from the forum but Can't find out the bug
I used bitmask+dp to solve the problem.
please help

[@li_kuet]

I have tried all the test case from the forum but Can't find out the bug
I used bitmask+dp to solve the problem.
please help

Code: Select all

Removed after AC :D :D

[brianfry713]

Input:

Code: Select all

3
8 16
8 11
9 16
0

AC output:

Code: Select all

**********************************************************
Network #1
Cable requirement to connect (8,11) to (8,16) is 21.00 feet.
Cable requirement to connect (8,16) to (9,16) is 17.00 feet.
Number of feet of cable required is 38.00.

[brianfry713]

http://acm.uva.es/board/viewtopic.php?t=10717

[Farsan]

MST should not work here because every node (except terminal nodes) must have exactly 2 edges but in mst any node can have any number of edges connected with it...

[brianfry713]

Don't find the MST. Each network has at least 2 and at most 8 computers. Use a brute force algorithm.