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


4.9 16 投票数
评分

圆上相交弦

测试数据下载:

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

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

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

然后按照从小到大排列

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

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

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

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

size()计算总的键的个数

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

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

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

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

最后sum就是答案

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

其他红黑树相关的问题

最大重叠点

2018-4-11 6
4.9 16 投票数
评分
61条留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
61 评论
内联反馈
查看所有评论
博丽灵梦
博丽灵梦 (@guest_201) Chrome 67.0.3396.62 Windows 10
游客
2018年12月27日 21:30

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

过路人
过路人(@4973682658c96f127bb6c779562a7708) Chrome 119.0.0.0 Windows 10
2023年11月21日 22:51

tql

sdsss
sdsss (@guest_3901) Chrome 106.0.0.0 Windows 10
游客
2022年10月31日 23:53
我对这篇文章的评分 :
     

看看rank怎么写

182****5363
182****5363(@b5a7b2556aae91891db7510f2933ab0f) Chrome 87.0.4280.141 Android 11 | V2048A
2022年10月30日 14:59
我对这篇文章的评分 :
     

牛牛牛

182****5363
182****5363(@b5a7b2556aae91891db7510f2933ab0f) Chrome 87.0.4280.141 Android 11 | V2048A
2022年10月30日 14:58
我对这篇文章的评分 :
     

tql

youwithme
youwithme (@guest_3897) Edge 106.0.1370.52 Windows 10
游客
2022年10月29日 15:47
我对这篇文章的评分 :
     

 ? 

youwithme
youwithme (@guest_3896) Edge 106.0.1370.52 Windows 10
游客
2022年10月28日 21:36
我对这篇文章的评分 :
     

tql

HeartCancer
HeartCancer(@8d2af8d0e50d3fd21f5f6732c4d16d12) Chrome 76.0.3809.89 Android 12 | M2012K10C
2022年10月22日 15:48

tql

1 4 5 6