### Problem Statement

You are developing a computer game where attack towers protect a city from approaching enemies. You need to calculate the damage that can be done to the enemy by a certain configuration of towers.

The towers are modeled as points on the X-Y plane. You are given int[]s towersX and towersY, where (towersX[i], towersY[i]) are the coordinates of the i-th tower. Each tower has an initial energy of damage and an effective radius of r.

When the enemy approaches, the towers attack as follows:

First, the towers can redistribute their energy. If the distance between two towers is less than or equal to r, one of them can transmit any amount of its energy to the other. When energy is transmitted between towers, half of it is lost. (So, if tower 1 transmits 10 energy to tower 2, tower 1 will lose 10 energy and tower 2 will receive only 5 energy.)

Then, the towers will attack. If the distance between the enemy and a tower is less than or equal to r, that tower can attack the enemy. When a tower attacks, all of its energy becomes damage to the enemy.

You are given the coordinates of the enemy as (enemyX, enemyY). Return the maximal total damage that can be done to the enemy.

### Definition

 Class: TowersAttack Method: maxDamage Parameters: int[], int[], int, int, int, int Returns: double Method signature: double maxDamage(int[] towersX, int[] towersY, int r, int damage, int enemyX, int enemyY) (be sure your method is public)

### Notes

-The amount of energy a tower can accumulate is unlimited.
-The returned value must have an absolute or relative error less than 1e-9.

### Constraints

-towersX will contain between 1 and 50 elements, inclusive.
-towersY will contain the same number of elements as towersX.
-Each element of towersX will be between 0 and 1000, inclusive.
-Each element of towersY will be between 0 and 1000, inclusive.
-All the towers' positions will be distinct.
-r will be between 1 and 500, inclusive.
-damage will be between 1 and 100, inclusive.
-enemyX will be between 0 and 1000, inclusive.
-enemyY will be between 0 and 1000, inclusive.
-The enemy's position will be distinct from all the towers' positions.

### Examples

0)

 `{2,4,6,8}` `{0,0,0,0}` `2` `10` `0` `0`
`Returns: 18.75`
 Tower 3 transmits 10 energy to tower 2 (tower 2 receives 5 energy). Then tower 2 transmits 15 energy to tower 1 (tower 1 receives 7.5 energy). Then tower 1 transmits 17.5 energy to tower 0 (tower 0 receives 8.75 energy). Finally, tower 0 attacks the enemy, and its 18.75 energy becomes damage.
1)

 `{5,6,5,3,1,0,1}` `{1,3,5,6,5,3,1}` `3` `100` `3` `0`
`Returns: 362.5`
2)

 `{2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8}` `{0,0,0,0,2,2,2,2,2,4,4,4,4,4,6,6,6,6,6,8,8,8,8,8}` `3` `1` `0` `0`
`Returns: 8.375`
3)

 `{1,2,3,4,5,3,3,3,3}` `{2,2,2,2,2,0,1,3,4}` `1` `4` `0` `2`
`Returns: 9.25`
4)

 `{0,10,5}` `{5,10,0}` `7` `17` `0` `0`
`Returns: 34.0`
5)

 `{10,12,10,8}` `{12,10,8,10}` `1` `100` `10` `10`
`Returns: 0.0`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8312

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10809&pm=8312

Nickolas

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

Geometry, Search