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 )↵
↵
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 )↵
