首页 > ACM题库 > HDU-杭电 > hdu 2165 Missile Command待解决[解题报告]C++
2013
12-30

hdu 2165 Missile Command待解决[解题报告]C++

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。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。