Minimum circle coverage problem
-
- Problem Description
- algorithm design
- Optimal substructure properties
- greedy selectivity
- code
Problem description
Original title link
There are some ships on the sea that need to communicate with the land, and some base stations need to be deployed on the coastline. Now abstract the problem as, above the x-axis, give the coordinates of N ships
p
1
,
p
2
,
…
,
p
N
,
p
i
=
(
x
i
,
y
i
)
,
0
≤
y
i
≤
d
,
1
≤
i
≤
N
,
p_1,p_2,…,p_N, p_i=(x_i,y_i), 0≤y_i≤d,1≤i≤N,
p1?, p2?,…,pN?, pi?=(xi?,yi?), 0≤yi?≤d,1≤i≤N, the base station placed on the x-axis can cover an area with a radius of d For all the points, at least several points must be placed on the x-axis to cover all the points above the x-axis. Try to design an algorithm to solve this problem and analyze the correctness of the algorithm.
Algorithm design
Sort the ships in order of x-coordinate from small to large. Traverse the sorted ships in order. If the current ship cannot be covered by the base station, build a new base station in the direction of increasing x so that the base station can just cover the ship.
Optimal substructure properties
Set up a ship
P
=
{
1
,
2
,
.
.
.
,
n
}
P = \{1, 2, …, n\}
P={1,2,…,n} has been sorted in increasing order of x-coordinate. Assume A is the optimal solution including base station 1, then A’ is the optimal solution to the sub-problem P′ composed of all remaining ships except the ship covered by base station 1. The number of base stations is
∣
A
‘
∣
=
∣
A
∣
?
1
|A’| = |A| – 1
∣A′∣=∣A∣?1.
The base stations in A’ can cover all ships. It only needs to be proved that the number of base stations in A’ is the minimum.
Suppose there is a better base station arrangement plan B’, which satisfies
∣
A
‘
∣
＞
∣
B
‘
∣
|A’| ＞ |B’|
∣A′∣>∣B′∣, then the optimal solution to the original problem should be
∣
B
‘
∣
+
1
＜
∣
A
‘
∣
+
1
|B’| + 1 < |A'| + 1 ∣B′∣ + 1＜∣A′∣ + 1, which is inconsistent with A being the optimal solution.
Therefore, the optimal solution to the problem contains the optimal solutions to the subproblems.
Greedy Selectivity
Set up a ship
P
=
{
1
,
2
,
.
.
.
,
n
}
P = \{1, 2, …, n\}
P={1,2,…,n} has been sorted in increasing order of x-coordinate.
Assume that there is an optimal solution A, in which the position of the first base station is not the position selected by the greedy algorithm, that is, it is not the rightmost position that can cover the first ship. Then, we can move the position of this base station to the right until it reaches the rightmost position that can cover the first ship, without reducing the number of ships it can cover. Therefore, the solution B obtained in this way is also an optimal solution, and the location of its first base station is the location selected by the greedy algorithm.
Assume that the position of the first base station selected by the greedy algorithm is x, and we remove the ships covered by this base station from the original problem to obtain a sub-problem. For this sub-problem, we can also use the above method to conclude that the first position selected by the greedy algorithm is an optimal solution. By continuing the above process, we can finally get the smallest scale sub-problem with the number of ships being 0. At this time, there is no need to place any base stations, which is obviously the optimal solution.
Through the above induction hypothesis, we can conclude that the greedy algorithm can obtain the optimal solution to this sub-problem.
Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef pair<int, int> PII;
int main()
{<!-- -->
int n, d;
while(cin >> n >> d & amp; & amp; (n || d)) {<!-- -->
vector<PII> p(n);
int x, y;
for(int i = 0; i < n; i + + ) {<!-- -->
cin >> x >> y;
p[i] = {<!-- -->x, y};
}
sort(p.begin(), p.end());
int res = 0, t;
for(auto it : p) {<!-- -->
if(res == 0 || (it.first - t)*(it.first - t) + it.second*it.second >= d*d) {<!-- -->
res++;
t = it.first + sqrt(d*d - it.second*it.second);
}
}
cout << res << endl;
}
return 0;
}