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 vector
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 vector 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 vector 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:vector , vector , vector , vector , vector , vector , int
Returns:int
Method signature:int minimumEnergyCost(vector canonX, vector canonY, vector
baseX, vector baseY, vector plantX, vector plantY, int energySupplyRadius)
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
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.