back to the menu

 Flag Counter

TopCoder SRM 543 - 1000: EllysDeathStars

Problem Statement

     题目简述：

在一个2D平面上，有一些飞船沿着各自的有向线段以各自的速度移动。它们同时出现在起点，一旦到达终点就消失。
一个飞船可以在攻击在它的射程范围内death star。
一个飞船在同一时间可以攻击多个death star。若攻击X个death star，需要消耗X点能量。
每个飞船有各自的初始能量值，如果能量不足则无法攻击。
同一时刻一个death star只能被一个飞船攻击，且它被攻击后不会消失，在下一时刻它依然能被攻击。
输入每个death star的坐标，和飞船的起点坐标、终点坐标、速度、射程、初始能量。
求所有飞船消耗能量总和的最大值。

数据范围：

death star个数不超过20个
飞船个数不超过20个



Princess Elly recently discovered secret plans for building a whole bunch of new death stars. Now she and the rebels are desperately trying to destroy them before they are fully operational.

They are sending several ships to destroy the death stars. For simplicity, in this problem the battle will take place in a 2D plane. The distances are so large that we will view all death stars and all ships as points in this plane. All death stars are stationary. All ships appear at their starting positions at the same time. Each ship is a point moving at some constant speed along some line segment, however the speeds for different ships may be different. As soon as a ship reaches the end of its segment, it disappears from the battlefield. (This does not necessarily happen at the same time for all the ships.) The rebels know the locations of all death stars. Also, for each ship they know its planned trajectory, its speed, the range of its lasers, and the amount of energy available for shooting them.

A ship can shoot at a death star if:
  • The death star is within its range
  • The ship still has energy for its lasers
Unfortunately, some defenses of the death stars are already active and prevent multiple ships from attacking the same death star at the same time. Thus, there is one additional rule:
  • No other ship is currently attacking the death star
On the other hand, all ships are able to shoot at multiple targets at the same time. Whenever a ship shoots at X targets at the same time, it consumes energy at the rate of X units per second. The ship can start and stop shooting at any target at any time. (The time spent shooting at a particular set of targets does not have to be an integer.)

You are given a vector <string> stars whose elements are formatted as "X Y", where (X, Y) corresponds to the position of one death star on the map. You are also given a vector <string> ships describing the ships. The i-th element of ships will be formated as "SX SY EX EY S R E", where (SX, SY) and (EX, EY) give the starting and ending point of the i-th ship, respectively, S is its speed, R is the range of its lasers, and E is its energy.

The rebels came up with a simple plan: They will shoot the death stars in such a way that the total amount of energy spent on shooting them is maximized. (It is possible that a different amount of energy will be spent on different death stars.) Compute and return the maximum total amount of energy spent by the ships' lasers if the rebels use an optimal shooting strategy.

Definition

    
Class:EllysDeathStars
Method:getMax
Parameters:vector <string>, vector <string>
Returns:double
Method signature:double getMax(vector <string> stars, vector <string> ships)
(be sure your method is public)

Limits

    
Time limit (s):2.000
Memory limit (MB):64

Notes

-Your return value must have a relative or an absolute error of less than 1e-9.
-The range of a ship's lasers is given in distance units (the same ones as all coordinates).
-The speed of a ship is given in distance units per second.
-A ship can have the same starting and ending point. Such ship disappears immediately after appearing on the battlefield.
-Multiple death stars can be located at the exact same place. They are still considered to be distinct death stars.
-Multiple ships can be located at the exact same place at some moment of time. A ship and a death star can be located at the exact same place at some moment of time. In both cases, no collision happens and each ship just proceeds moving along its defined trajectory.

Constraints

-stars will contain between 1 and 20 elements, inclusive.
-Each element of stars will contain between 3 and 9 characters, inclusive.
-Each element of stars will be formated as "X Y" - two space-separated integers between 1 and 1000, inclusive.
-ships will contain between 1 and 20 elements, inclusive.
-Each element of ships will contain between 13 and 34 characters, inclusive.
-Each element of ships will be formated as "SX SY EX EY S R E" - seven space-separated integers between 1 and 1000, inclusive.

Examples

0)
    
{"2 2"}
{"1 1 5 3 2 1 2"}
Returns: 0.894427190999916
Just a single ship and a single star. The ship has plenty of energy, so it might shoot at the death star the whole time it is in range.
1)
    
{"12 10", "7 5"}
{"10 10 12 10 1 1 3", "6 1 8 10 1 2 3", "3 6 8 2 5 3 1", "42 42 42 42 6 6 6"}
Returns: 4.983770744659944
Although the first ship has remaining energy, it disappears before it can shoot it all. The last ship disappears right after the beginning.
2)
    
{"5 77", "60 50", "10 46", "22 97", "87 69"}
{"42 17 66 11 5 7 13", "10 10 20 20 3 3 3", "13 15 18 9 4 1 2",
 "99 71 63 81 19 4 60", "27 34 56 43 11 3 12"}
Returns: 0.0
Plenty of ships and stars, but no action whatsoever.
3)
    
{"141 393", "834 847", "568 43", "18 228", "515 794",
 "167 283", "849 333", "719 738", "434 261", "613 800",
 "127 340", "466 938", "598 601"}
{"410 951 472 100 337 226 210", "713 352 677 908 731 687 300",
 "191 41 337 92 446 716 213", "598 889 446 907 148 650 203",
 "168 556 470 924 344 369 198", "300 182 350 936 737 533 45",
 "410 871 488 703 746 631 80", "270 777 636 539 172 103 56",
 "466 906 522 98 693 77 309", "768 698 846 110 14 643 14",
 "755 724 664 465 263 759 120"}
Returns: 31.965770956316362
Random testcase.

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)2003, TopCoder, Inc. All rights reserved.