#P2177. Ghost Busters

Ghost Busters

题目描述

著名的捉鬼敢死队决定为他们的 ecto - 1(又名 “捉鬼车”)升级,配备强大的质子枪和先进的瞄准系统。埃贡(Egon)已经设计并制造好了所有硬件,包括外质扫描仪和一个具有两个自由度的质子枪,该质子枪能在 90 度三面角内自动旋转并射击。你受雇为该瞄准软件编写一个原型。 幽灵由外质扫描仪检测到,并表示为浮球。它们球心的坐标和半径会从外质扫描仪传输到瞄准软件。坐标系已校准,质子枪从点 (0,0,0)(0, 0, 0)X0Y0Z0X ≥ 0、Y ≥ 0、Z ≥ 0 的三面角内的任意方向射击。质子枪发射的质子射线是直线,且威力巨大,只要射线擦过幽灵就能将其消灭。质子枪的射线在其路径上理论上可以消灭数量无限的幽灵。 对于瞄准软件的第一个原型,你需要编写一个程序,确定质子枪一次射击能够消灭的幽灵的最大数量。

输入

输入的第一行是一个整数 N0N100N(0 ≤ N ≤ 100),即ecto1 ecto - 1 的外质扫描仪检测到的幽灵数量。接下来的 N 行描述检测到的幽灵,每行描述一个幽灵。第 i 个幽灵(幽灵从 1 到 N 编号)的描述由 4 个整数 XiYiZiRiX_i、Y_i、Z_i 和 R_i 组成,用空格分隔。XiYiZi1Xi,Yi,Zi10000X_i、Y_i、Z_i(1 ≤ X_i, Y_i, Z_i ≤ 10000)是幽灵球心的坐标,Ri1Rimin(Xi,Yi,Zi)R_i(1 ≤ R_i ≤ min (X_i, Y_i, Z_i))是幽灵的半径。由于幽灵是由外质构成的,它们可以任意放置,可能会相互交叉、一个包含在另一个内部、相互重合等等。

输出

在输出的第一行,输出一个整数,即质子枪一次射击能够消灭的幽灵的最大数量。在输出文件的第二行,按任意顺序输出要消灭的幽灵的编号,用空格分隔。如果有多种消灭此数量幽灵的方法,输出其中任意一种即可。