
圆上相交弦
测试数据下载:
下载提示
这道题还是要用到红黑树来做
数学上可以证明下面给出的算法是正确的,但是证明从略,只给出操作步骤
首先把每个端点(一共2n个)与原点的夹角求出来
然后按照从小到大排列
之后从0度开始 ,逆时针顺序扫描
如果扫描到的某个点,与它在同一弦上的另一个端点不曾出现在红黑树中,这个端点看作起点,把这个端点的夹角作为key加入到红黑树
如果这个点在同一弦上的另一个端点已经出现在红黑树中,这个点认为是终点,然后看看比对应起点的key更大的key有多少个
其中rank()
计算严格小于给定键的键有多少个
size()
计算总的键的个数
由于题目保证不可能出现相同的键
所以,比对应起点的key更大的key有多少个,等于size()-rank()-1
加到sum
,然后从红黑树删除这个起点和终点
如此循环,直到2n个点全部扫一遍
最后sum
就是答案
此区域的内容需评论后可见
其他红黑树相关的问题
其实是道树状数组/线段树就能解决的题
@博丽灵梦你好,是的,可以使用线段树直接解决,但是我们的专业课需要要求使用红黑树实现。
So cool!
跳起来
tql
谢谢长老
学习一个
谢谢
tqll
tql
大佬你的QQ是多少呢 我想详细点问您这道题方便嘛
@123博客主页有我的 QQ。现在很久没写那种难度的题了,已经退化了……
请问线段树该怎么做呢 可以给个思路吗
@123核心思路是两条弦相交只需要保证“其中一条的一个点在另一条的两个端点之间”。红黑树、树状数组、线段树做法都是类似的,都是维护一下前 n 个数有多少个左/右端点。