## 216 - Getting in Line

Moderator: Board moderators

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am

### 216 - Getting in Line

[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]

ei01036
New poster
Posts: 12
Joined: Wed Jan 15, 2003 1:13 am
i'm having the same problem...
if anyone knows of something that could help, pls post!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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.

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

### hi everybody

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]

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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).

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

### thx

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]

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
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!!!

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

### ???

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]
Last edited by pavelph on Fri Jan 02, 2004 1:26 pm, edited 1 time in total.

Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
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.

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

### AC!

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.

IBelieve
New poster
Posts: 14
Joined: Sun Nov 16, 2003 7:40 pm

### 216 help needed

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]
When people agree with me I always feel that I must be wrong.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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.

watershed
New poster
Posts: 13
Joined: Thu Aug 05, 2004 9:14 am

### Re: AC!

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.``````

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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.