LZN树————强于平衡树

时间:2021-07-20 15:14:40

 

 

圆锥玩具

问题描述

 

xqz小朋友家中堆积了好多好多种玩具,其中一种便是圆锥玩具。他经常将这类玩具混乱的摆在地上,欣赏内在的排列美。

他先把圆锥垂直放在地面上。这些圆锥都有一个特点,就是它的半径等于高度,且内部是空心的,底面也是空的。xqz小朋友有时会将其中的一些小的圆锥玩具放到比它大的圆锥玩具里,如果一个圆锥玩具不被另外任意一个圆锥完全包裹着,xqz就会格外喜欢它(…)

你的任务便是帮助xqz小朋友找出所有他格外喜欢的玩具。(特别的,如果两个圆锥的底面相切,小的圆锥也算被包裹着)为了简化模型,我们将地面抽象成二维平面。

 

输入文件

 

第一行一个正整数N,表示玩具个数。

接下来N行,每行3个实数,rixiyi,表示圆锥底面的半径和坐标。(其中hi=rihi表示圆锥的高度),第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 rixiyi ≤ 109ri为正数。

 

 

 

 

 

本来要用平衡树的一道题,被LZN树给解决了,瞬间压了代码,有兴趣的同学可以去试试打平衡树。

本树由LZN大牛发明,故命名为LZN树......

 

 

LZN树核心思想:

以每个圆的最左边的端点为第一关键字,半径为第2关键字,快排一便。

然后从左至右搜,一旦超出范围即可BREAK。

效率的话,我用多组数据测试过了,虽然理论复杂度是N^2,但由于LZN树的特殊优化性,可以将实际复杂度压至理论的1/12000左右,甚至超过了打平衡树的同学,在所有测试点中,平均比平衡树快大约2倍,感谢LZN大牛! 

 

          

 

 

猥琐的标程:

 

 

友情链接:http://blog.csdn.net/woshitanwei/archive/2011/05/20/6434582.aspx