Problem Statement |
| | The celebrated general Archibald Waving took charge of the fourth army in the occidental front. After losing the first three armies, Waving has become obsessed with efficient energy consumption. He has thus started innovating in what he calls "green warfare". He will use his newly acquired philosophy in an attempt to win the final battle of the occidental front. The development of death rays has been useful for Waving's side, but the plutonium required to shoot is scarce. The enemy side has bases and energy plants of its own and thus Waving has decided to take the initiative and destroy the enemy's forces once and for all, but using as little energy as possible.
The general has assigned you to determine how to accomplish this feat. Your main objective is to neutralize each of the enemy bases. A base is considered neutralized either if it was destroyed by a death ray or if all the energy plants supplying to it have been destroyed. There are a number of death ray canons that you can use and each canon may shoot multiple targets if necessary but can only destroy a single target with each shoot. The positions of the canons are given by two int[]s: canonX and canonY where the i-th canon is located at the point (canonX[i],canonY[i]). You can make each canon shoot a certain target at any distance but the energy required per target is equal to: d*d gigajoules where d is the euclidean distance between the target and the canon. The bases' positions are described by int[]s baseX and baseY where the i-th base is located at the point (baseX[i],baseY[i]), and the energy plants' locations are described by int[]s plantX and plantY where the i-th energy plant is located at the point (plantX[i],plantY[i]). An energy plant supplies energy to an enemy base if and only if the euclidean distance between them is less than or equal to energySupplyRadius. Return the minimum amount of energy required (in gigajoules), to neutralize all enemy bases.
|
| |
Definition |
| | | Class: | GreenWarfare | | Method: | minimumEnergyCost | | Parameters: | int[], int[], int[], int[], int[], int[], int | | Returns: | int | | Method signature: | int minimumEnergyCost(int[] canonX, int[] canonY, int[] baseX, int[] baseY, int[] plantX, int[] plantY, int energySupplyRadius) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | baseX, baseY, canonX, canonY, plantX and plantY will each contain between 1 and 50 elements, inclusive. |
| - | baseX and baseY will contain the same number of elements. |
| - | canonX and canonY will contain the same number of elements. |
| - | plantX and plantY will contain the same number of elements. |
| - | The position given for each canon, base and energy plant will be unique. |
| - | Each element in baseX, baseY, canonX, canonY, plantX and plantY will be between -500 and 500, inclusive. |
| - | energySupplyRadius will be between 1 and 2000, inclusive. |
| - | Every base will be within energySupplyRadius distance units to at least one energy plant. |
| |
Examples |
| 0) | |
| | { 0 } | { 0 } | {1,2,3} | {0,0,0} | {3} | {3} | 4 |
| Returns: 14 | | Use the canon to destroy each base individually, the costs are: 1, 4 and 9 gigajoules. The total cost is 14 gigajoules. |
|
|
| 1) | |
| | { 0 } | { 0 } | {1,2,3} | {0,0,0} | {2} | {2} | 4 |
| Returns: 8 | | In this case, the distance between the energy plant and the canon is smaller and the new optimal strategy is to destroy the energy plant with a cost of 8 gigajoules. |
|
|
| 2) | |
| | {3,6} | {3,6} | {1,2,3,4,5} | {5,4,2,3,1} | {1,2,5} | {1,2,5} | 5 |
| Returns: 12 | | Use the first canon to destroy the first two energy plants, use the second canon to destroy the remaining one. |
|
|
| 3) | |
| | {0} | {0} | {-10,-10,10} | {10,-10,0} | {10,10,-10} | {10,-10,0} | 10 |
| Returns: 200 | | Destroy the base at (10,0) and the energy plant at (-10,0), 200 gigajoules are required in total. |
|
|
| 4) | |
| | {0} | {0} | {3} | {3} | {1,2,3} | {0,0,0} | 4 |
| Returns: 14 | |
|