In this problem we model a simple power grid. As input, we are given n houses, represented
Fantastic news! We've Found the answer you've been seeking!
Question:
In this problem we model a simple power grid. As input, we are given n houses, represented by n pairs of positive integers (x1, y1), (x2, y2), · · · , (xn, yn) which are their coordinates in the plane. We are also given a list of m power plants. Each power plant is represented by
- a) A pair of positive integers (ai,bi) representing their coordinates in the plane.
- b) A positive integer ri, representing the maximum distance to which the power plant
- can send power (measured by standard Euclidean distance).
- c) A positive integer ci, representing the number of houses that power plant can simultaneously power.
Design an algorithm to solve the following problem: given a list of n houses and m power plants as described above, decide if it is possible to connect each house to each power plant such that all houses receive power and no power plant is over its capacity.
Related Book For
Probability and Statistical Inference
ISBN: 978-0321923271
9th edition
Authors: Robert V. Hogg, Elliot Tanis, Dale Zimmerman
Posted Date: