UVA1313 Ghost Busters

题目描述

在立体空间的第一象限内($x,y,z\ge0$)有许多的球,有些互相重叠,有些互相包含。假设我们从原点(0,0,0)发出一条射线。现在我们要求,这条射线最多能穿过几个球(穿过边界也算)。

输入格式

输入一个 $T$,表示有 $T$ 组数据。 每组数据首先输入整数 $N$,$0\le N\le100$。 接下来 $N$ 行,每行用四个整数描述一个球,分别是它的圆心坐标和它的半径。并且数据保证没有任何一个球的表面会超出第一象限。

输出格式

输出的第 1 行一个整数,表示最多穿过多少个球。第二行若干个数,表示这些球的编号。 ### 输入输出样例 输入: ``` 2 2 1200 1200 3900 300 160 160 820 60 13 1200 1200 3900 300 160 160 820 60 100 10 10 10 10 100 10 10 10 10 100 10 10 10 10 10 50 50 50 10 100 100 75 20 100 75 100 20 75 100 100 20 3000 4000 7000 2600 100 1000 1000 50 1000 100 1000 100 ``` 输出: ``` 2 1 2 5 6 7 9 10 11 ```