2013
12-30

# Missile Command

As Chief Bureaucrat at Missile Command, it has recently come to your attention that the existing performance guidelines do not sufficiently penalize frivolous use of expensive ammunition. Therefore, you must write a new battle summary analysis tool which takes into account excess ammunition consumption during battle.

A battle consists of the following elements:
�  Shots. A shot is a circularly explosive countermeasure. A shot has a fixed position and a duration of 2 seconds, during which its radius varies from 0 to 1km and then back to 0 according to the formula:
r = (1 � (t � 1)2)1/2
�  The ground, at y = 0.
�  Missiles. A missile is a point particle that moves at a constant velocity. If a missile collides with a shot, it is neutralized. If a missile hits the ground before being neutralized, it is considered to have hit its target.
�  NOTE 1: If a missile hits a shot, the shot does not disappear � it may hit other missiles
�  NOTE 2: Shots of 0 radius cannot hit missiles (e.g. a missile will go through an already expired shot).

Performance is evaluated on a simple point scale. The performance criteria are as follows:
�  Every neutralized missile adds 1 point.
�  Every missile allowed to hit its target subtracts 5 points.
�  Every unnecessary shot subtracts 20 points. The number of unnecessary shots in a battle is the difference between the actual number of shots fired and size of the minimum subset of those shots that would have neutralized the same number of missiles.

Input will be given in the following format (legend follows):
nb
nm
mx my mdx mdy mt

ns
sx sy st

In the following legend, indentation denotes repetition of the indented block a number of times equal to the value of the preceding input item:
nb (0 < nb) � number of battles
nm (0 <= nm <= 20) � number of missiles
mx/my (0.0 < my) � initial missile position (in km)
mdx/mdy � missile velocity (in km/s)
mt (0.0 <= mt) � time since battle start of the missile’s entrance (in seconds)
ns (0 <= ns <= 20) � number of shots
sx/sy (1.0 <= sy) � shot position at time of detonation (in km)
st (0.0 <= st) � time since battle start of the shot’s detonation (in seconds)

Input will be given in the following format (legend follows):
nb
nm
mx my mdx mdy mt

ns
sx sy st

In the following legend, indentation denotes repetition of the indented block a number of times equal to the value of the preceding input item:
nb (0 < nb) � number of battles
nm (0 <= nm <= 20) � number of missiles
mx/my (0.0 < my) � initial missile position (in km)
mdx/mdy � missile velocity (in km/s)
mt (0.0 <= mt) � time since battle start of the missile’s entrance (in seconds)
ns (0 <= ns <= 20) � number of shots
sx/sy (1.0 <= sy) � shot position at time of detonation (in km)
st (0.0 <= st) � time since battle start of the shot’s detonation (in seconds)

2
2
4.0 8.0 0.0 -1.0 0.0
4.0 8.0 1.0 -1.0 0.0
1
4.0 4.0 3.0
3
4.0 10.0 0.0 -1.0 0.0
5.0 10.0 3.0 -6.0 4.0
13.0 10.0 -3.0 -5.0 4.0
3
4.0 5.0 3.0
7.0 8.0 4.0
9.0 4.0 4.0

-4
-17

1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

2. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。