You are given an infinite 2-D grid.
There are:
N fixed points on the grid that must be lit.
K types of light towers.
Each tower type i has:
- A cost per unit distance ki (for each one unit of radius, the cost is ki)
You may place any number of towers of any type at any grid position.
You may choose any non-negative radius r for each placed tower.
You can use each tower at most once.
If you place a tower of type i with radius r, then: - It lights all points within distance r from its position. - Its cost is: r * ki
A fixed point is considered lit if it lies within the radius of at least one placed tower.
Your task is to light all N fixed points with minimum total cost.
Constraints 1 <= N <= 2*10^5,
1 <= K <= 2*10^5,
-1e9 <= xi, yi <= 1e9,
1 <= ki <= 1e9
distance between two point : dist(a, b) = sqrt( (ax — bx)^2 + (ay — by)^2 )
Auto comment: topic has been updated by Rankit (previous revision, new revision, compare).
Can the towers only be placed on integer coordinates?
Why would we use any tower types other than the one with minimum $$$k_i$$$ if we can place an unlimited number of towers of each type?
no no no, each tower can be used at most once. And it's not necessary to place only on integer coordinates.
is this missing some constraints? you can achieve total cost of zero by placing a tower with any cost at each of the N fixed points and setting r = 0.
Auto comment: topic has been updated by Rankit (previous revision, new revision, compare).
Are you sure this is not $$$NP$$$-Hard? The $$$K=1$$$ case is https://cp-algorithms.com/geometry/enclosing-circle.html, and I don't see an obvious way to extend the solution to multiple circles.