本文写于 2018年04月11日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


5 9 投票数
评分

圆上相交弦

测试数据下载:

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

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

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

然后按照从小到大排列

之后从0度开始 ,逆时针顺序扫描

如果扫描到的某个点,与它在同一弦上的另一个端点不曾出现在红黑树中,这个端点看作起点,把这个端点的夹角作为key加入到红黑树

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

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

size()计算总的键的个数

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

所以,比对应起点的key更大的key有多少个,等于size()-rank()-1

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

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

最后sum就是答案

此区域的内容需评论后可见

其他红黑树相关的问题

最大重叠点

2018-4-11 6
5 9 投票数
评分
49条留言
订阅评论
提醒
guest
您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。
49 评论
内联反馈
查看所有评论
博丽灵梦
博丽灵梦
游客
2018年12月27日 21:30

其实是道树状数组/线段树就能解决的题

optx
游客
2021年10月21日 23:46
我对这篇文章的评分 :
     

tql

1 10 11 12