作业|学习|模板|算法|题解

圆上相交弦

凝神长老 · 4月11日 · 2018年 3342次已读

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


5 3 投票
评分

圆上相交弦

测试数据下载:

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

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

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

然后按照从小到大排列

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

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

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

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

size()计算总的键的个数

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

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

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

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

最后sum就是答案

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

其他红黑树相关的问题

最大重叠点

2018-4-11 6
5 3 投票
评分
5 3 投票
评分
订阅评论动态
提醒
guest
43 评论
最新
最旧 得票最多
行内反馈
查看所有评论
博丽灵梦
博丽灵梦 Chrome 67.0.3396.62 Windows 10
2018年12月27日 21:30

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

666
666 Safari 605.1.15 Mac OS X Lion 10_15_7
2020年11月10日 13:33
我对这篇文章的评分 :
     

跳起来

niu
niu Chrome 86.0.4240.111 Windows 10
2020年10月31日 21:16
我对这篇文章的评分 :
     

tql

Once
Once Chrome 86.0.4240.111 Windows 10
2020年10月29日 17:56
我对这篇文章的评分 :
     

谢谢长老

SmallY
SmallY Edge 86.0.622.43 Windows 10
2020年10月20日 15:03

学习一个

匿名
匿名 Firefox 71.0 Windows 10
2020年1月3日 22:27

谢谢

aa
aa Chrome 78.0.3904.108 Windows 10
2019年12月8日 11:37

tqll

hhh
hhh QQ 6.5.5 Android 9 | HUAWEI BLA-AL00
2019年12月4日 23:57

tql

123
123 Chrome 76.0.3809.132 Windows 10
2019年11月30日 13:38

大佬你的QQ是多少呢 我想详细点问您这道题方便嘛

123
123 Chrome 76.0.3809.132 Windows 10
2019年11月30日 12:10

请问线段树该怎么做呢 可以给个思路吗

123
123 Chrome 76.0.3809.132 Windows 10
2019年11月30日 12:10

请问线段树应该怎么做呢

123
123 Chrome 76.0.3809.132 Windows 10
2019年11月29日 16:23

膜一下大佬

Kuroko
Kuroko Chrome 77.0.3865.90 Windows 10
2019年10月12日 10:20

tql

lll
lll Edge 18.18362 Windows 10
2019年10月12日 09:51

tql

啦啦啦
啦啦啦 Chrome 77.0.3865.90 Windows 10
2019年10月11日 14:57

ttttql

kuroko
kuroko Firefox 69.0 Windows 10
2019年10月10日 20:58

菜鸟Kuroko前来抄作业了·-·

ewqe
ewqe Chrome 77.0.3865.90 Windows 10
2019年10月8日 18:38

tql

lll
lll Chrome 73.0.3683.103 Android 9 | HMA-AL00
2019年10月8日 16:52

tql

a
a Chrome 69.0.3497.100 Windows 10
2019年9月27日 18:38

tql

azdas
azdas Chrome 70.0.3538.67 Linux
2019年5月21日 15:28

tql

hcy226
hcy226 Chrome 73.0.3683.75 Windows 10
2019年4月8日 23:31

nb

ABC666
ABC666 Chrome 61.0.3163.128 Android 8.0.0 | MI 6
2018年12月18日 22:07

tql

czczc
czczc Chrome 62.0.3202.94 Windows 10
2018年12月10日 18:40

tttql

czc
czc Chrome 62.0.3202.94 Windows 10
2018年12月10日 18:39

tql

哈哈黄瓜
哈哈黄瓜 Firefox 63.0 Windows 10
2018年12月7日 17:27

zzwtql

哈哈怪
哈哈怪 Firefox 63.0 Windows 10
2018年12月7日 17:27

您tql

Zoey
Zoey Chrome 64.0.3282.186 Windows 10
2018年12月1日 19:46

666

e
e Firefox 63.0 Windows 10
2018年11月2日 18:52

1

dlgd
dlgd Chrome 70.0.3538.77 Windows 10
2018年10月31日 22:15

不会做,听说这里有题解

deerbean
deerbean Chrome 70.0.3538.77 Windows 10
2018年10月31日 19:48

again

1099
1099 Edge 17.17134 Windows 10
2018年10月30日 22:09

33

109
109 QQ 7.8.2.435 iPhone iPhone OS 12_0 like Mac OS X) AppleWebKit
2018年10月30日 18:12

g g

Sixuan
Sixuan Chrome 70.0.3538.77 Windows 8
2018年10月30日 13:50

tql

deerbean
deerbean Edge 12.10240 Windows 10
2018年10月29日 16:35

ttttttql

mmm
mmm Chrome 69.0.3497.100 Windows 10
2018年10月22日 20:02

tql

bloodmaster
bloodmaster Firefox 62.0 Windows 10
2018年10月22日 15:15

tql

k
k Firefox 61.0 Windows 10
2018年10月13日 15:05

TQL

Griffith_Fu
Griffith_Fu Chrome 69.0.3497.100 Windows 10
2018年10月8日 23:24

tql

_
_ Chrome 66.0.3359.181 Windows 10
2018年9月28日 13:28

retql

_
_ Chrome 69.0.3497.100 Windows 10
2018年9月28日 11:39

tql