
圆上相交弦
测试数据下载:
下载提示
这道题还是要用到红黑树来做
数学上可以证明下面给出的算法是正确的,但是证明从略,只给出操作步骤
首先把每个端点(一共2n个)与原点的夹角求出来
然后按照从小到大排列
之后从0度开始 ,逆时针顺序扫描
如果扫描到的某个点,与它在同一弦上的另一个端点不曾出现在红黑树中,这个端点看作起点,把这个端点的夹角作为key加入到红黑树
如果这个点在同一弦上的另一个端点已经出现在红黑树中,这个点认为是终点,然后看看比对应起点的key更大的key有多少个
其中rank()
计算严格小于给定键的键有多少个
size()
计算总的键的个数
由于题目保证不可能出现相同的键
所以,比对应起点的key更大的key有多少个,等于size()-rank()-1
加到sum
,然后从红黑树删除这个起点和终点
如此循环,直到2n个点全部扫一遍
最后sum
就是答案
此区域的内容需评论后可见
其他红黑树相关的问题
其实是道树状数组/线段树就能解决的题
@博丽灵梦你好,是的,可以使用线段树直接解决,但是我们的专业课需要要求使用红黑树实现。
tql
看看rank怎么写
牛牛牛
tql
?
tql
tql