The Jedi Battalion
All submissions for this problem are available.
The war between the Jedi’s and the Empire Battle Droids is at its height. Master Yoda, bored from this war, wants to end this as soon as possible, while using minimum Jedi powers. To discuss the battle plans, he calls a meeting of all the Jedi Masters at the Jedi Temple. There, the Jedis start meditating and get connected to each other using telepathy. To maximise their power, they enclose a closed region using these telepathic connections. Telepathy is a tricky business, the Jedi’s can somehow connect to each other with the shortest distance possible in real world.
The droids somehow come to know of this meeting and plan to kill the Jedis in the Temple. But as they approach the Temple, the Jedis become aware of their presence. Master Yoda doesn’t want to waste precious Jedi powers on these droids. He asks each Jedi warrior how much power would he need to use in order to kill each droid.
To calculate the power needed to kill a droid, a Jedi cuts himself from the other Jedis and observes if a droid is inside the telepathic region, so formed. If the droid falls inside it, the power required to kill him is equal to the manhattan distance between the Jedi and that droid. If not, the power required is equal to the square of Euclidean distance between them.
Master Yoda decides to launch an attack before its too late, so he assigns each Jedi a particular drone to kill such that the total Jedi power required by them is maximised.
The first line contains a single integer N, which denotes the number of Jedi Masters (=Number of Empire Battle Droids)
The next N lines contain two space separated integers X Y, the location of the Jedi Masters.
The next N lines contain the two space separated integers X Y, the location of the battle droids.
A single integer K denoting the maximum total Jedi power that is required.
- 5 ≤ N ≤ 350
- 1 ≤ X,Y ≤ 1000
Input: 5 2 1 3 2 3 4 1 4 1 2 2 2 3 3 3 1 4 3 4 1 Output: 41
|Time Limit:||0.48731 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions