(巨人和鬼问题) 有n个巨人正与n个鬼战斗。每个巨人..._

(巨人和鬼问题)  有n个巨人正与n个鬼战斗。每个巨人的武器是一个质子包，  它可以用一串质子流射中鬼来把鬼消灭。质子流沿直线行进，在击中鬼时就终止。巨人央定采取下列策略。他们各自寻找-一个鬼形成n个巨人一鬼对，然后每个巨人同时向各自选取的鬼射出一串质子流。  我们知道，质子流互相交叉是很危险的，  因此，  巨人选择的配对方式应该使质子流都不会交叉。
  假定每个巨人和每个鬼的位置都是平面上一个固定的点，并且没有三个位置共线。
a.  论证存在一条通过一个巨人和一个鬼的直线，使得直线一边的巨人数与同一边的鬼数相等。试说明如何在O(n lg n)时间内找出这样一条直线。
b.写出一个运行时间为O(n² lg n)的算法，  使其以不会有质子流交叉为条件把巨人与鬼配对。

(巨人和鬼问题) 有n个巨人正与n个鬼战斗。每个巨人...

问题信息

热门推荐

相关试题