2268. Kitchen Robot
Robots are
becoming more and more popular. They are used nowadays not only in
manufacturing plants, but also at home. One programmer with his friends decided
to create their own home robot. As you may know most programmers like to drink
beer when they gather together for a party. After the
party there are a lot of empty bottles left on the table. So, it was decided to
program robot to collect empty bottles from the table.
The table is a
rectangle with the length l and width w. Robot starts at the
point (xr, yr) and n bottles are located at points (xi,
yi)
(1 ≤ i ≤ n). To collect a bottle robot
must move to the point where the bottle is located, take it, and then bring to
some point on the border of the table to dispose it. Robot can hold only one
bottle at the moment and for simplicity of the control
program it is allowed to release bottle only at the border of the table.
You can assume
that sizes of robot and bottles are negligibly small (robot and bottles are
points), so the robot holding a bottle is allowed to move through the point
where another bottle is located.
One of the
subroutines of the robot control program is the route planning. You are to
write the program to determine the minimal length of robot route needed to
collect all the bottles from the table.
Input. The first line contains two integer
numbers w
and l (2 ≤ w, l ≤ 1000) – the width and
the length of the table.
The second line
contains an integer number n (1 ≤ n
≤ 18) – the number of bottles on the table. Each of the following n lines contains two integer numbers xi and yi –
coordinates of the i-th bottle (0
< xi < w, 0 < yi < l). No two bottles are located
at the same point.
The last line
contains two integer numbers xr and yr (0 < xr < w, 0 < yr < l) – coordinates of the robot’s
initial position. Robot is not located at the same point with a bottle.
Output. Print the length of the shortest route of the robot. Your answer should
be accurate within an absolute error of 10-6.
|
Sample input |
Sample output |
3 421 12 3
2 1 |
5.60555127546399 |
SOLUTION
dynamic programming – TSP problem
Algorithm analysis
Let A and B be two bottles that will be
sequentially collected by the robot from the table. After the robot picks up
bottle A, it must throw it out at one of the four table boundaries. Only then
robot will go for bottle B. Let us find the shortest path of the robot from
point A(xi, yi) to
B(xj,
yj)
with an approach to the edge of the table.
Distance AK + KB = AK + KP = AP. Taking into account the coordinates of points A(xi, yi) and P(xj, -yj), we
obtain
AP = 
= 
Distance AL + LB = AL + LQ = AQ. The
abscissa of point Q is w + (w – xj) = 2w – xj. Taking
into account the coordinates of points A(xi, yi) and Q(2w
– xj,
yj),
we obtain
AQ = 
Distance AE + EB = AE + ET = AT. Taking into account the coordinates of points A(xi, yi) and T(-xj, yj), we
obtain
AT = 
= 
Distance AD + DB = AD + DS = AS. The
ordinate of point S is l + (l – yj) = 2l – yj. Taking
into account the coordinates of points A(xi, yi) and S(xj, 2l
– yj),
we obtain
AS = 
Find the smallest distance required to
throw one bottle located at the point (xi,
yi)
over the edge of the table. It is equal to the minimum of four segments:
min( xi,
yi,
w – xi, l – yi)
This will be the path that the robot must
travel to throw the last bottle away.
The initial position of the robot and the
coordinates of the bottles are given. Consider a graph, the zero vertex of
which corresponds to the initial position of the robot, and the remaining
vertices correspond to the bottles. The distance between vertex zero and other
vertices equals to the Euclidean distance between points. The distance between
bottles i and j is equal to the minimum path along which one can go from bottle i to bottle j, having visited the edge of the table. Since there are n bottles on the table, the graph will
contain n + 1 vertices.
Next, you need to find the minimum length of
the Hamiltonian path in a graph. At the end, when the robot reaches the last
bottle, the path required to throw this bottle over the edge of the table
should be added to the final result. We’ll find for
the desired Hamiltonian path using dynamic programming with masks with
complexity O(n2 * 2n).
Robot’s initial
position and bottles’ positions are given below.
The length of the shortest route of the robot is
1 + 
+ 1 = 2 + 
≈ 5.605
Algorithm realization
Declare a constant infinity INF and the
maximum number of points in the Hamiltonian path MAX.
#define INF 1e18
#define MAX 20
Declare
an array dp, where we’ll store
dynamically recomputed values dp(S, i). Store the bottle
coordinates at the points (xi, yi) (1 ≤ i ≤ n). Store the initial position of the
robot in (x0, y0).
double dp[1 << MAX][MAX +
1];
double x[MAX], y[MAX], m[MAX][MAX];
Function solve computes the
value dp(S, last), where the set S is encoded by the
integer mask. Moreover, S \ {last} equals to mask ^
(1<< last). Next, iterate over all i, i Î S \ {last} and
look for the minimum value res among dp(S \ {last}, i)
+ m[i][last]. The variable res points to the
cell dp[mask][last], so when res changes,
the value of dp[mask][last] also changes.
double solve(int mask, int last)
{
double
&res = dp[mask][last];
if (res
== INF)
{
mask ^=
(1 << last);
for (int i =
1; i < n; i++)
if ((mask
& (1 << i)) && (i != last))
res =
min(res, solve(mask, i) + m[i][last]);
}
return res;
}
Function
f
returns the shortest distance from the point (x[i], y[i]) to the edge of
the table.
double f(int i)
{
return
min(min(x[i], y[i]), min(l - y[i], w
- x[i]));
}
Function dist
returns the distance between the points (x[i],
y[i]) è (x[j], y[j]).
double dist(int i, int j)
{
return
sqrt((x[i] - x[j])*(x[i] -
x[j]) +
(y[i] -
y[j])*(y[i] - y[j]));
}
The
main part of the program. Read the size of the table w and l.
scanf("%d %d",
&w, &l);
Read
the number of bottles n and their
coordinates (x[i], y[i]).
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%lf
%lf", &x[i + 1], &y[i + 1]);
The
initial coordinates of the robot store in (x[0], y[0]).
scanf("%lf %lf",
&x[0], &y[0]);
Add
a zero vertex to n bottles – the initial
position of the robot. After increasing by one, n contains the number of vertices in the graph. The vertices of the
graph are numbered 0, 1, …, n – 1.
n++;
Compute
the pairwise distances between the bottles. The distance between bottles i and j is equal to the minimum path along which one can go from bottle i to bottle j, having visited the edge of the table.
for (i = 1; i < n - 1; i++)
for (j = i + 1; j < n; j++)
m[i][j] =
m[j][i] =
min(
min(sqrt((x[i] + x[j])*(x[i] + x[j]) + (y[i] -
y[j])*(y[i] - y[j])),
sqrt((2 *
w - x[i] - x[j])*(2 * w - x[i] - x[j]) +
(y[i]
- y[j])*(y[i] - y[j]))),
min(sqrt((x[i]
- x[j])*(x[i] - x[j]) + (y[i] + y[j])*(y[i] + y[j])),
sqrt((x[i]
- x[j])*(x[i] - x[j]) +
(2 *
l - y[i] - y[j])*(2 * l - y[i] - y[j])))
);
Initially,
the values of dp(S, i) are unknown, set them equal to plus
infinity.
for (i = 0; i < 1 << n; i++)
for (j = 0; j < n; j++)
dp[i][j] = INF;
The
set {0} corresponds to the mask 1, set dp({0}, 0) = 0 (the minimum
path from the zero vertex to it without visiting other vertices is equal to zero). Store
the required minimum length of Hamiltonian path in the variable total.
dp[1][0] = 0; total = INF;
for (i = 1; i < n; i++) dp[1 | (1
<< i)][i] = dist(0, i);
Compute the
Hamiltonian cycle of minimum length. The value 2n – 1
corresponds to the set {0, 1, 2, ..., n – 1}. Compute the
minimum among all values of dp({0, 1, 2, ..., n –
1}, i) + f(i), 1 £ i < n.
After computing the minimum length of the Hamiltonian path, add the distance
that the robot must travel to throw the last i-th bottle off the table boundary – it equals
to f(i).
for (i = 1; i < n; i++)
total =
min(total, solve((1 << n) - 1, i) + f(i));
Print
the required minimum length.
printf("%.6lf\n",
total);