圆锥玩具
问题描述
xqz小朋友家中堆积了好多好多种玩具,其中一种便是圆锥玩具。他经常将这类玩具混乱的摆在地上,欣赏内在的排列美。
他先把圆锥垂直放在地面上。这些圆锥都有一个特点,就是它的半径等于高度,且内部是空心的,底面也是空的。xqz小朋友有时会将其中的一些小的圆锥玩具放到比它大的圆锥玩具里,如果一个圆锥玩具不被另外任意一个圆锥完全包裹着,xqz就会格外喜欢它(…)。
你的任务便是帮助xqz小朋友找出所有他格外喜欢的玩具。(特别的,如果两个圆锥的底面相切,小的圆锥也算被包裹着)为了简化模型,我们将地面抽象成二维平面。
输入文件
第一行一个正整数N,表示玩具个数。
接下来N行,每行3个实数,ri,xi,yi,表示圆锥底面的半径和坐标。(其中hi=ri,hi表示圆锥的高度),第i行为第i个玩具。
输入数据仅保证任意两个圆锥的底面不相交且不重合,不保证不相切。
输出文件
第一行一个数M,表示xqz格外喜欢的玩具的个数。
第二行M个数,输出玩具的编号,从小到大输出,以空格隔开。
输入样例
5
1 0 -2
3 0 3
10 0 0
1 0 1.5
10 50 50
输出样例
2
3 5
数据规模和约定
对于20%的数据,N ≤ 500。
对于100%的数据,N ≤ 100000,-109 ≤ ri,xi,yi ≤ 109,ri为正数。
本来要用平衡树的一道题,被LZN树给解决了,瞬间压了代码,有兴趣的同学可以去试试打平衡树。
本树由LZN大牛发明,故命名为LZN树......
LZN树核心思想:
以每个圆的最左边的端点为第一关键字,半径为第2关键字,快排一便。
然后从左至右搜,一旦超出范围即可BREAK。
效率的话,我用多组数据测试过了,虽然理论复杂度是N^2,但由于LZN树的特殊优化性,可以将实际复杂度压至理论的1/12000左右,甚至超过了打平衡树的同学,在所有测试点中,平均比平衡树快大约2倍,感谢LZN大牛!
猥琐的标程:
友情链接:http://blog.csdn.net/woshitanwei/archive/2011/05/20/6434582.aspx