Page 1 of 4

### 216 - Getting in Line

Posted: Fri Jun 14, 2002 2:55 am
[cpp]#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

double df(double a,double b)
{
return sqrt(a*a+b*b);
}

void main()
{
int i,j,N,z;
vector<vector<double> > dist;
vector<pair<int,int> > points;
vector<int> enumeration,ShortestPath;
double Shortest,Current;

z=0;

while(scanf("%d",&N)!=EOF&&N>0)
{
z++;
dist=vector<vector<double> >(N,vector<double>(N,0));
points.resize(N);
enumeration.clear();
Shortest=100000;
for(i=0;i<N;i++)
{
scanf("%d%d",&points.first,&points.second);
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(i!=j)
{
dist[j]=df(points.first-points[j].first,points.second-points[j].second)+16;
}
}
}
for(i=0;i<N;i++)
{
enumeration.push_back(i);
}
do
{
Current=0;
for(i=1;i<N;i++)
{
Current+=dist[enumeration[i-1]][enumeration];
}
if(Current<Shortest)
{
Shortest=Current;
ShortestPath=enumeration;
}
}
while(next_permutation(enumeration.begin(),enumeration.end()));
printf("**********************************************************\n");
printf("Network #%d\n",z);
for(i=1;i<N;i++)
{
printf("Cable requirement to connect (%d,%d) to (%d,%d) is %3.2lf feet.\n",points[ShortestPath[i-1]].first,points[ShortestPath[i-1]].second,points[ShortestPath].first,points[ShortestPath].second,dist[ShortestPath[i-1]][ShortestPath]);
}
printf("Number of feet of cable required is %3.2lf.\n",Shortest);
}
}[/cpp]

Posted: Thu Feb 20, 2003 8:15 pm
i'm having the same problem... if anyone knows of something that could help, pls post!

Posted: Thu Jul 31, 2003 2:17 pm
I've got Acc on this problem, but with time circa 0.5 sec ...
Could anyone help me and tell how can I improve this time ?? I use brute force, because I don't know any other method ...

Best regards
DM

Posted: Thu Jul 31, 2003 4:38 pm
RE: C8H10N4O2's code

Not sure if the board did this or not or if that is how the code is actually formatted, but remove the carriage return between "Cable requirement... %3.2lf" and the next line "feet" and add a space in between.

Otherwise, I don't see anything wrong with your code. I randomly generated 10,000 test cases and checked it against my AC code, and there is no difference between the two outputs after the above change.

RE: Optimizing

I have 0.040s, which is fast, but not the fastest for this problem. The only real optimization I do is, do the permutations myself instead of using C++'s next_permutation function, which allows me to prune the tree whenever the current distance of the links is greater than any minimum I've already found.

### hi everybody

Posted: Thu Aug 14, 2003 11:47 am
first of all sorry about my english .. well, i try to solve this problem using the next permutation funcion too, but judge always rpelies me WA and i can't see my mistake, can anybody help me plz? thx a lot

[cpp]

#include <iostream>
#include <vector>
#include <utility>
#include <math.h>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;

long double dist2(pair<int,int> x, pair<int,int> y)
{
return sqrt(((x.first-y.first)*(x.first-y.first))+((x.second-y.second)*(x.second-y.second)));
}

long double dist(vector<pair<int,int> > v)
{
if(v.size() < 2)
return 0;
long double totalDist = 0;
for(int i = 0; i < v.size()-1; i++)
totalDist += dist2(v,v[i+1]);
}

vector<pair<int,int> > SP(vector<pair<int,int> > points)
{
vector<pair<int,int> > res;
long double min = 1000000000, minAux;
if(points.size() == 2)
return points;
while(next_permutation(points.begin(),points.end()))
{
minAux = dist(points);
if(minAux < min)
{
res = points;
min = minAux;
}
}
return res;
}

void output(vector<pair<int,int> > shortestPath, int _case)
{
long double totalDist = 0 ;
cout << "**********************************************************" << endl;
cout << "Network #" << _case << endl;
for(int i = 0; i < shortestPath.size()-1; i++)
{
long double aux = dist2(shortestPath,shortestPath[i+1])+16;
cout << "Cable requirement to connect ("
<< shortestPath.first << "," << shortestPath.second << ") to ("
<< shortestPath[i+1].first << "," << shortestPath[i+1].second << " ) is " ;
printf("%.2f",aux);
cout << " feet." << endl;
totalDist += aux;
}
printf("Number of feet of cable required is %.2f.\n",totalDist);
}

void proces(vector<pair<int,int> > points, int _case)
{
vector<pair<int,int> > shortestPath;
shortestPath = SP(points);
output(shortestPath, _case);
}

int main()
{
int numPoints, _case = 1;
cin >> numPoints;
while(numPoints != 0)
{
vector<pair<int,int> > points(numPoints);
for(int i = 0; i < numPoints; i++)
cin >> points.first >> points.second;
proces(points, _case++);
cin >> numPoints;
}
return 0;
}
[/cpp]

Posted: Fri Aug 15, 2003 7:16 am
Oriol:

Input:

Code: Select all

``````6
111 84
55 28
43 116
38 101
28 62
5 19``````
Output as in first sample input case (i.e. 305.45 feet).

### thx

Posted: Fri Aug 15, 2003 9:29 am
well,
first i must sort the points, thx, but i'm WA again, can anybody test again my code? [cpp]

#include <iostream>
#include <vector>
#include <utility>
#include <math.h>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;

long double dist2(pair<int,int> x, pair<int,int> y)
{
return sqrt(((x.first-y.first)*(x.first-y.first))+((x.second-y.second)*(x.second-y.second)));
}

long double dist(vector<pair<int,int> > v)
{
if(v.size() < 2)
return 0;
long double totalDist = 0;
for(int i = 0; i < v.size()-1; i++)
totalDist += dist2(v,v[i+1]);
}

vector<pair<int,int> > SP(vector<pair<int,int> > points)
{
vector<pair<int,int> > res;
long double min = 1000000000, minAux;
sort(points.begin(),points.end());
min = dist(points);
res = points;
while(next_permutation(points.begin(),points.end()))
{
minAux = dist(points);
if(minAux < min)
{
res = points;
min = minAux;
}
}
return res;
}

void output(vector<pair<int,int> > shortestPath, int _case)
{
long double totalDist = 0 ;
cout << "**********************************************************" << endl;
cout << "Network #" << _case << endl;
for(int i = 0; i < shortestPath.size()-1; i++)
{
long double aux = dist2(shortestPath,shortestPath[i+1])+16;
cout << "Cable requirement to connect ("
<< shortestPath.first << "," << shortestPath.second << ") to ("
<< shortestPath[i+1].first << "," << shortestPath[i+1].second << ") is " ;
printf("%.2f",aux);
cout << " feet." << endl;
}
totalDist = dist(shortestPath) + (16*(shortestPath.size()-1));
printf("Number of feet of cable required is %.2f.\n",totalDist);
}

void proces(vector<pair<int,int> > points, int _case)
{
vector<pair<int,int> > shortestPath;
shortestPath = SP(points);
output(shortestPath, _case);
}

int main()
{
int numPoints, _case = 1;
cin >> numPoints;
while(numPoints != 0)
{
vector<pair<int,int> > points(numPoints);
for(int i = 0; i < numPoints; i++)
cin >> points.first >> points.second;
proces(points, _case++);
cin >> numPoints;
}
return 0;
}
[/cpp]

Posted: Sun Dec 21, 2003 1:52 am
Sorry, I haven`t ACC for this problem and I can`t understand smth: for
input

Code: Select all

``````6
111 84
55 28
43 116
38 101
28 62
5 19
0
``````
output

Code: Select all

``````**********************************************************
Network #5
Cable requirement to connect (111,84) to (43,116) is 91.15 feet.
Cable requirement to connect (43,116) to (38,101) is 31.81 feet.
Cable requirement to connect (38,101) to (28,62) is 56.26 feet.
Cable requirement to connect (28,62) to (55,28) is 59.42 feet.
Cable requirement to connect (55,28) to (5,19) is 66.80 feet.
Number of feet of cable required is 305.45.
``````
, not "as in first sample input case". Help me please!!!

### ???

Posted: Mon Dec 22, 2003 6:18 pm
I read on the list of problems that 216 has Special Judge. What does it mean? Here my code, that works on all inputs, but getting me WA.
[pascal]{CODE CUT}[/pascal]

Posted: Tue Dec 23, 2003 12:38 pm
In a normal problem there is only one solution to a specific input.
So the judge simply creates two output from the judge input.
It then compares the two files. If the files matches then you get
AC, WA otherwise.

A special judge means that for a specific input there are multiple
valid solutions and any one of them will do. So the judge program
get your output for the judge input. But it does not compare it with
judge output rather it reads in your output and check for consistency
of your output against the input. If the output is consistent then you get
AC, WA otherwise.

What it really means that don't worry if your output don't exactly match
with judge output/sample output. You will get AC as long as it is correct.

Right now I don't have time to go through with your code. As soon as I'm
free I will look into it for error.

Sorry for such long explanation. I can't seem to explain things in short
like others do. ### AC!

Posted: Fri Jan 02, 2004 1:31 am
Thank you.
I`m found my mistake: I didn`t understood condition of problem. I thougth that first computer fixed.
Now I got AC!!! Thanks.

### 216 help needed

Posted: Mon Jan 26, 2004 3:13 pm
Why do I get WA ? It works on my computer and produses right answers for the sample outputs provided ...

[pascal]
program GettingInLine;
var si,s:array [1..1000] of integer;
x,y:array [1..1000] of integer;
a,r:real;
stars:string;
visited:array [1..1000] of boolean;
function dist(x1,y1,x2,y2:real):real;
begin
dist:=sqrt(sqr(x2-x1)+sqr(y2-y1))+16;
end;
procedure backtrack(n,i:integer;d:real);
var k:integer;
begin
if (i = N+1) then
if (D<R) then begin R:=D;Si:=S end else begin end else
for k:=1 to n do
begin
s:=k;
if not visited[k] then
begin
visitedt[k]:=true;
if i>1 then
a:=D+Dist(x[S],y[S],x[S[i-1]],y[S[i-1]])
else a:=0;
if (a<=R) then
backtrack(n,i+1,a);
visited[k]:=false;
end;
end;
end;
var i:integer;
begin
for i:=1 to n do
end;
var nr,i,n:integer;
begin
stars:='**********************************************************';
nr:=1;
R:=maxint;
while (n<>0) do
begin
backtrack(n,1,0);
writeln(Stars);
writeln('Network #',nr);
for i:=2 to n do
writeln('Cable requirement to connect (',x[Si[i-1]],',',y[Si[i-1]],') to (',x[Si],',',y[Si],') is ',dist(x[Si[i-1]],y[Si[i-1]],x[Si],y[Si]):2:2,' feet.');
writeln('Number of feet of cable required is ',R:2:2,'.');
R:=maxint;
end;
end;
begin
end.
[/pascal]

Posted: Mon Jan 26, 2004 4:47 pm
About your tagline: I don't agree with you, but that doesn't mean you're right...

About your posting: Why do you post it here and not in the forum for volume 2?

in procedure backtrack you use visitedt[k] in stead of visited[k] on one occasion...

Your program will get accepted if you print the appropriate network number in stead of "Network #1:" for every network.

### Re: AC!

Posted: Thu Aug 05, 2004 5:08 pm
if input is..

Code: Select all

``````2
100 100
100 100``````

Code: Select all

``````**********************************************************
Network #1
Cable requirement to connect (100,100) to (100,100) is 16.00 feet.
Number of feet of cable required is 16.00.``````

Code: Select all

``````**********************************************************
Network #1
Cable requirement to connect (100,100) to (100,100) is 0.00 feet.
Number of feet of cable required is 0.00.``````

Posted: Thu Aug 05, 2004 5:31 pm
My program outtputed the first one, but it shouldn't matter since the description states that:
No two computers are at identical locations and each computer will be listed once.