圆上相交弦 – jxtxzzw个人博客

圆上相交弦

4月11日 · 2018年

圆上相交弦

测试数据下载:

这道题还是要用到红黑树来做

数学上可以证明下面给出的算法是正确的,但是证明从略,只给出操作步骤

首先把每个端点(一共2n个)与原点的夹角求出来

然后按照从小到大排Copyright Reserved @jxtxzzw

之后从0度开始 ,逆时这是jxtxzzw的个人博客针顺序文章由jxtxzzw原创扫描

如果扫描到的某个点,与它在同一弦上的另一个端点不曾出现在红黑https://www.jxtxzzw.com树中,这个端请勿采集与复制,转载请注明出处点看作起点,把这个端点的夹角作为key加入到红黑树

如果反采集功能启动这个点在同一弦上的另一个端点已经出现在红黑树中,这个点认为是终点,然后看看比对应起点的key更大的key有多少个

其中rank()计算严格小于给定键的键有多少个

反采集功能启动size()计算总的键的个数

由于题目保证不可能出现相同的键

所以,比对应起点的key更大的key有多少https://www.jxtxzzw.com个,等于size()-rank()-1

加到sum,然后从红黑树删除这个起点和终点

如此循环,直到2n个点全部扫一遍

最后sum就是答案

此区域的内容仅评论后可见
0 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定