Pizza Delivery
Time limit1sMemory limit128 MB
Choose at most K of M candidate sites to maximize the total population within radius R, counting each building once even if covered multiple times.
- Level
Medium6 of 10
- Topics
- Combinatorics, Brute force, Geometry
- Solved
- No attempts yet
Problem
Picko wants to open pizza restaurants that provide delivery. There are M candidate restaurant locations, and there are N residential buildings with known populations.
A restaurant can deliver to every residential building whose Euclidean distance from that restaurant is at most R. Picko may open at most K restaurants at the candidate locations. If a building is covered by more than one restaurant, its population is counted only once.
Compute the maximum number of people who can be covered by delivery.
Input
The first line contains two integers K and R, the maximum number of restaurants and the delivery radius (1 <= K <= 10, 1 <= R <= 500).
The second line contains an integer M, the number of candidate restaurant locations (K <= M <= 20).
Each of the next M lines contains two integers X and Y, the coordinates of one candidate location (-1000 <= X, Y <= 1000).
The next line contains an integer N, the number of residential buildings (1 <= N <= 100).
Each of the next N lines contains three integers X, Y, and S. Here, X and Y are the coordinates of a residential building, and S is the number of people living there (-1000 <= X, Y <= 1000, 1 <= S <= 100). A residential building is covered by a restaurant if the distance between them is at most R.
No two candidate restaurant locations have the same coordinates.
Output
Print one integer: the maximum number of people who can be covered by delivery.