2 shunfurh shunfurh 于 2017.09.03 00:07 提问

Ghost Busters

The famous Ghost Busters team has decided to upgrade their Ectomobile (aka Ecto-1) with a powerful proton gun and an advanced targeting system. Egon has designed and built all the hardware which consists of ectoplasmic scanner and a proton gun that has two degrees of freedom and can automatically rotate and fire in a 90 degrees trihedral angle. You have been hired to write a prototype for the targeting software.

Ghosts are detected by ectoplasmic scanner and are represented as floating spheres. The coordinates of their centers and radii are delivered from the ectoplasmic scanner to the targeting software. The coordinate system is aligned in such a way, that the proton gun fires from the point (0, 0, 0) anywhere into X >= 0, Y >= 0, Z >= 0 trihedral angle. The gun fires a proton ray in a straight line and is so powerful, that even a touch of its ray is enough to kill a ghost. The ray of the proton gun is able to kill a virtually unlimited number of ghosts on its way.

For the first prototype for the targeting software, you are asked to write a program that determines the maximal number of ghosts that can be killed with a single shot of the proton gun.

Input

On the first line of the input file there is a single integer number N (0 <= N <= 100) - the number of ghosts detected by the ectoplasmic scanner of Ecto-1. The following N lines describe detected ghosts - one ghost per line. The description of ith ghost (ghosts are numbered from 1 to N) consists of 4 integer numbers Xi, Yi, Zi, and Ri, separated by spaces. Xi, Yi, Zi (1 <= Xi, Yi, Zi <= 10000) are the coordinates of the ghost's center, and Ri (1 <= Ri <= min(Xi, Yi, Zi)) is the ghost's radius. Because ghosts are ectoplasmic, they can be arbitrarily placed in respect to each others. They can intersect, fit inside each other, coincide with each other, etc.

Process to the end of file.

Output

On the first line of the output file write a single integer number - the maximal number of ghosts that can be killed with a single shot of the proton gun. On the second line of the output file write the identifying numbers of the ghosts to be killed in an arbitrary order separated by spaces. If there are multiple ways to kill this number of ghosts then write any one.

Sample Input

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

Sample Output

2
1 2
5
6 7 9 10 11

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.17 22:41
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Little Busters Ex(LBEX) 修改工具(任意剧情查看工具)
此程序运行需要 .netframework 2.0(Vista  win7 已经自带) (注意权限问题,Vista和7 UAC开启时无法修改NTFS分区上的文件)   感谢 爱神的礼物,此工具只适用 CK小组汉化版   修改作用: 可以任意查看剧情,或者说可以任意攻略剧情   使用修改 请放到游戏目录下 运行 修改以后(修改完别忘记保存。) 运行游戏 -> New Game
UVa 109 - SCUD Busters(凸包)
题意:输入n个国家,每个国家一些点,用围墙(多边形)围起来,围墙内的范围都属于这个国家,现在要发射一些导弹,如果导弹落到国家内,那对应的国家就会停电,现在问停电的总面积。 分析:1,求凸包,Graham扫描先把围墙上的点求出来,凸包完成。 2,求国家的面积,把多边形分成多个三角形,叉积a*b*sin就是三角形面积的两倍,然后相加求得多边形面积。 3,判断点是否在多边形内,用射线进行判断,从该
Rita - Little busters!
[ar:Rita][ti:Little Busters!][00:00.01]Little busters![00:13.38] [00:14.26]作詞/作曲:麻枝准 編曲:中沢伴行/尾崎武士[00:20.62]歌:Rita[00:39.96]ひとりが辛(つら)いからふたつの手(て)をつないだ[00:46.29]ふたりじゃ寂(さび)しいから輪(わ)になって手(て)をつないだ[00:52.00
poj 1264 || UVA 109 SCUD Busters
UVA这题过得蛮多人的,觉得应该是个水题吧。 一读题,也不麻烦,给你N个王国,求下凸包,再求面积。给你一些炮弹,问炮弹炸掉的面积。(一个炮弹炸的话,整个王国都被炸了)。 直接求凸包后,求出各个王国的面积,然后判断炮弹在哪个王国里,这个直接用判断点是否在多边形内。 UVA WA了一次,如果多个炮弹打到同一个王国里,面积只算一次的,改了后,A掉了。 poj上一搜,居然也
codeforces 382B B. Number Busters [二分答案+数学]【思维】
题目链接:http://codeforces.com/contest/382/problem/B—————————————————————————————————-. B. Number Busters time limit per test1 second memory limit per test256 megabytes inputstandard input outputstand
UVa 109 - SCUD Busters
题目:红警0 0?有一些国家,给出国家被围墙围了起来,围墙内的范围都属于这个国家,现在要发射一些导弹,如果导弹落到国家内,那对应的国家就会停电,现在问停电的总面积。 分析:计算几何、凸包、点与多边形关系。首先、利用围墙构造出每个国家的凸包,求出凸包面积;然后、对于每个导弹枚举凸包,判断个导弹是否落在凸包内是的话加到总面积上即可。            点在多边形内的判断:做几条射线(即与无限远
POJ 1264 SCUD Busters (凸包面积+判断点是否在凸包内)
POJ 1264 SCUD Busters (凸包面积+判断点是否在凸包内)
用Ghost搭建自己的博客
用Ghost搭建自己的博客 本人最近在学习Java以及Spring框架,为了让自己开发的小网站能跑在云端,于是就在阿里云上买了台与服务器以及域名,买了之后好像用的也不多,觉得挺浪费的,于是就想到了在云服务器上搭建一个博客,用来记录自己平时学习或工作中遇到的问题及心得,我不奢求这个博客能够多么火爆,但如果这个上面的信息能够帮助到有需要的人,我还是非常开心的(好像扯远了~)。 网上的博客系
Blockchain的鱼和熊掌系列(4)GHOST协议
It is well acknowledged that optimizing the tradeoff between performance and security in a given computing system is always a challenging work.Perhaps the most important work in a Blockchain is the tra
Ghost blog的文件迁移
使用Ghost搭建的blog的文件迁移。