The city plans to
eliminate unattractive electrical poles by laying cables underground. A list of
points that must be connected is given, but there are certain constraints. The
tunneling equipment can move only along straight lines between the specified
points. At any location other than the given points, at most one underground
cable may pass, therefore no two cables are allowed to intersect.
A set of points
is given. Determine the minimum total length of cable required so that every
pair of points is connected either directly or through other points.
Input. Contains multiple test cases. Each test case
begins with an integer n (2 ≤ n ≤ 1000) – the number of
points in the city. Each of the following n lines contains two integers
x and y (-1000 ≤ x, y ≤ 1000) – the coordinates of a point (x, y). All points
within a single test case are distinct. The last line contains 0 and should not
be processed.
Output. For each test case, print one real number – the
minimum length of cable required to connect all city points, printed with
accuracy to two decimal places.
|
Sample input |
Sample
output |
|
4 0 0 0 10 10 0 10 10 2 0 0 10 10 0 |
30.00 14.14 |
graphs – Prim algorithm
To solve the problem, it is
necessary to find a minimum spanning tree. For this purpose, we implement
Prim’s algorithm.
Example
Let us construct the two
graphs given in the example.
Declare global arrays. The
coordinates of the points will be stored in the arrays x[i] and y[i].
#define MAX 1001
#define INF 0x3F3F3F3F
int x[MAX], y[MAX];
int used[MAX], dist[MAX];
The
function dist2 computes the squared distance between points i and j.
int dist2(int i, int j)
{
return (x[j] -
x[i])*(x[j] - x[i]) +
(y[j] - y[i])*(y[j] -
y[i]);
}
The
Prim function implements Prim’s algorithm and
returns the weight of the minimum spanning tree.
double Prim(void)
{
Initialize
the arrays.
memset(dist, 0x3F, sizeof(dist));
memset(used, 0, sizeof(used));
We
start constructing the minimum spanning tree from vertex 0. Set dist[0] = 0 and used[0] = 1. The variable res
accumulates the total weight of the minimum spanning tree.
double res = 0;
int i, j, cur = 0;
dist[cur]
= 0;
used[cur]
= 1;
We
perform n – 1
iterations. At each iteration, we add one vertex to the spanning tree (thus, a
total of n – 1 vertices must be added).
for (i = 1; i < n; i++)
{
The
current vertex is denoted as cur. We iterate
over the edges (cur, j) and update the values of dist[j].
As a result, dist[j] stores the current shortest distance from vertex j
to the already constructed part of the minimum spanning tree.
for (j = 0; j < n; j++)
if (!used[j] && (dist2(cur, j) < dist[j]))
dist[j] = dist2(cur, j);
We
search for the edge of minimum length to be added to the spanning tree. To do
this, we find the minimum value of dist[j] among the vertices j
that do not yet belong to the tree (used[j] = 0). The index of the
vertex with the minimum dist[j] value is stored in the variable cur,
which becomes the current vertex.
int min = INF;
for (j = 0; j < n; j++)
if (!used[j] && (dist[j] < min))
{
min = dist[j];
cur = j;
}
The
vertex cur is then included in the spanning tree, and the edge of length
sqrt(dist[cur]) is added to the minimum spanning tree.
used[cur]
= 1;
res +=
sqrt(dist[cur]);
}
return res;
}
The
main part of the program. Process the test cases sequentially.
while (scanf("%d", &n), n)
{
Read
the coordinates of the points.
for (i = 0; i < n; i++)
scanf("%d %d", &x[i], &y[i]);
Compute
and print the weight of the minimum spanning tree.
res = Prim();
printf("%.2lf\n", res);
}
Declare global arrays. The
coordinates of the points will be stored in the arrays x[i] and y[i].
#define MAX 1010
int x[MAX], y[MAX];
int used[MAX],
min_e[MAX], end_e[MAX];
The
function dist2 computes the squared distance between points i and j.
int dist2(int i, int j)
{
return (x[j] -
x[i])*(x[j] - x[i]) +
(y[j] - y[i])*(y[j] -
y[i]);
}
The
main part of the program. Process the test cases sequentially.
while (scanf("%d",
&n), n)
{
Read
the coordinates of the points.
for (i =
0; i < n; i++)
scanf("%d
%d", &x[i], &y[i]);
Initialize
the arrays.
memset(min_e, 0x3F, sizeof(min_e));
memset(end_e, -1, sizeof(end_e));
memset(used, 0, sizeof(used));
The
weight of the minimum spanning tree will be accumulated in the variable dist.
dist
= min_e[1] = 0;
for (i =
0; i < n; i++)
{
We
find the vertex v with the
minimum value min_e[v] among the vertices that have not yet been included in the minimum
spanning tree (used[v] = 0).
v =
-1;
for (j =
0; j < n; j++)
if
(!used[j] && (v == -1 || min_e[j] < min_e[v])) v = j;
Include
the vertex v in the
spanning tree and add the edge (v, end_e[v]).
used[v]
= 1;
if
(end_e[v] != -1) dist += sqrt((double)dist2(v,
end_e[v]));
Update
the labels for the edges (v, to) outgoing from vertex v. The iteration is performed only
over the vertices to that have not yet been included
in the minimum spanning tree (used[to] =
0).
for (to
= 0; to < n; to++)
{
int
dV_TO = dist2(v, to);
if
(!used[to] && (dV_TO < min_e[to]))
{
min_e[to] = dV_TO;
end_e[to] = v;
}
}
}
Print
the weight of the minimum spanning tree.
printf("%.2lf\n",
dist);
}