#P2177. Ghost Busters
Ghost Busters
题目描述
著名的捉鬼敢死队决定为他们的 ecto - 1(又名 “捉鬼车”)升级,配备强大的质子枪和先进的瞄准系统。埃贡(Egon)已经设计并制造好了所有硬件,包括外质扫描仪和一个具有两个自由度的质子枪,该质子枪能在 90 度三面角内自动旋转并射击。你受雇为该瞄准软件编写一个原型。 幽灵由外质扫描仪检测到,并表示为浮球。它们球心的坐标和半径会从外质扫描仪传输到瞄准软件。坐标系已校准,质子枪从点 向 的三面角内的任意方向射击。质子枪发射的质子射线是直线,且威力巨大,只要射线擦过幽灵就能将其消灭。质子枪的射线在其路径上理论上可以消灭数量无限的幽灵。 对于瞄准软件的第一个原型,你需要编写一个程序,确定质子枪一次射击能够消灭的幽灵的最大数量。
输入
输入的第一行是一个整数 ,即的外质扫描仪检测到的幽灵数量。接下来的 N 行描述检测到的幽灵,每行描述一个幽灵。第 i 个幽灵(幽灵从 1 到 N 编号)的描述由 4 个整数 组成,用空格分隔。是幽灵球心的坐标,是幽灵的半径。由于幽灵是由外质构成的,它们可以任意放置,可能会相互交叉、一个包含在另一个内部、相互重合等等。
输出
在输出的第一行,输出一个整数,即质子枪一次射击能够消灭的幽灵的最大数量。在输出文件的第二行,按任意顺序输出要消灭的幽灵的编号,用空格分隔。如果有多种消灭此数量幽灵的方法,输出其中任意一种即可。