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

圆上相交弦

jxtxzzw · 4月11日 · 2018年 2544次已读

圆上相交弦

测试数据下载:

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

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

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

然后按照从小到大排列

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

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

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

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

size()计算总的键的个数

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

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

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

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

最后sum就是答案

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

其他红黑树相关的问题

最大重叠点

2018-4-11 6

共 39 条评论
说点什么

avatar

您可以根据需要插入表情、图片、音频、视频或者其他附件,也可以 @ 你需要提及的用户

  
不开心么么什么再见加油发火可以可怜可爱吐吐血吓呵呵哈哈哦哭哼喜欢嗯嘿嘿困圣诞坏笑圣诞调皮坏笑女汉子奸笑好的委屈宝宝害羞小清新心塞快哭了恭喜发财惆怅我最美抓狂抠鼻放空无奈晕汗泪奔温柔女生狗年生气笑笑泪衰调皮调皮女生鄙视酷静静额鼓掌
上传图片
 
 
 
上传视频和音频
 
 
 
上传其他类型文件
 
 
 
36 评论主题数
3 评论回复数
0 评论跟进人数
 
最近回复的评论
最热烈的讨论
28 评论人数
0aahhhjxtxzzw123 最近评论者

  订阅评论动态  
最新 最旧 得票最多
提醒
    博丽灵梦
    博丽灵梦
    离线
    1 年 之前 [2018-12-27 · 21:30]
    Chrome 67.0.3396.62 Windows 10

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

    匿名
    匿名
    离线
    2 月 之前 [2020-1-3 · 22:27]
    Firefox 71.0 Windows 10

    谢谢

    aa
    aa
    离线
    3 月 之前 [2019-12-8 · 11:37]
    Chrome 78.0.3904.108 Windows 10

    tqll

    hhh
    hhh
    离线
    3 月 之前 [2019-12-4 · 23:57]
    QQ 6.5.5 Android 9 | HUAWEI BLA-AL00

    tql

    123
    123
    离线
    4 月 之前 [2019-11-30 · 13:38]
    Chrome 76.0.3809.132 Windows 10

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

    123
    123
    离线
    4 月 之前 [2019-11-30 · 12:10]
    Chrome 76.0.3809.132 Windows 10

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

    123
    123
    离线
    4 月 之前 [2019-11-30 · 12:10]
    Chrome 76.0.3809.132 Windows 10

    请问线段树应该怎么做呢

    123
    123
    离线
    4 月 之前 [2019-11-29 · 16:23]
    Chrome 76.0.3809.132 Windows 10

    膜一下大佬

    Kuroko
    Kuroko
    离线
    5 月 之前 [2019-10-12 · 10:20]
    Chrome 77.0.3865.90 Windows 10

    tql

    lll
    lll
    离线
    5 月 之前 [2019-10-12 · 9:51]
    Edge 18.18362 Windows 10

    tql

    啦啦啦
    啦啦啦
    离线
    5 月 之前 [2019-10-11 · 14:57]
    Chrome 77.0.3865.90 Windows 10

    ttttql

    kuroko
    kuroko
    离线
    5 月 之前 [2019-10-10 · 20:58]
    Firefox 69.0 Windows 10

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

    ewqe
    ewqe
    离线
    5 月 之前 [2019-10-8 · 18:38]
    Chrome 77.0.3865.90 Windows 10

    tql

    lll
    lll
    离线
    5 月 之前 [2019-10-8 · 16:52]
    Chrome 73.0.3683.103 Android 9 | HMA-AL00

    tql

    a
    a
    离线
    6 月 之前 [2019-9-27 · 18:38]
    Chrome 69.0.3497.100 Windows 10

    tql

    azdas
    azdas
    离线
    10 月 之前 [2019-5-21 · 15:28]
    Chrome 70.0.3538.67 Linux

    tql

    hcy226
    hcy226
    离线
    11 月 之前 [2019-4-8 · 23:31]
    Chrome 73.0.3683.75 Windows 10

    nb

    ABC666
    ABC666
    离线
    1 年 之前 [2018-12-18 · 22:07]
    Chrome 61.0.3163.128 Android 8.0.0 | MI 6

    tql

    czczc
    czczc
    离线
    1 年 之前 [2018-12-10 · 18:40]
    Chrome 62.0.3202.94 Windows 10

    tttql

    czc
    czc
    离线
    1 年 之前 [2018-12-10 · 18:39]
    Chrome 62.0.3202.94 Windows 10

    tql

    哈哈黄瓜
    哈哈黄瓜
    离线
    1 年 之前 [2018-12-7 · 17:27]
    Firefox 63.0 Windows 10

    zzwtql

    哈哈怪
    哈哈怪
    离线
    1 年 之前 [2018-12-7 · 17:27]
    Firefox 63.0 Windows 10

    您tql

    Zoey
    Zoey
    离线
    1 年 之前 [2018-12-1 · 19:46]
    Chrome 64.0.3282.186 Windows 10

    666

    e
    e
    离线
    1 年 之前 [2018-11-2 · 18:52]
    Firefox 63.0 Windows 10

    1

    dlgd
    dlgd
    离线
    1 年 之前 [2018-10-31 · 22:15]
    Chrome 70.0.3538.77 Windows 10

    不会做,听说这里有题解

    deerbean
    deerbean
    离线
    1 年 之前 [2018-10-31 · 19:48]
    Chrome 70.0.3538.77 Windows 10

    again

    1099
    1099
    离线
    1 年 之前 [2018-10-30 · 22:09]
    Edge 17.17134 Windows 10

    33

    109
    109
    离线
    1 年 之前 [2018-10-30 · 18:12]
    未知浏览器 未知操作系统

    g g

    Sixuan
    Sixuan
    离线
    1 年 之前 [2018-10-30 · 13:50]
    Chrome 70.0.3538.77 Windows 8

    tql

    deerbean
    deerbean
    离线
    1 年 之前 [2018-10-29 · 16:35]
    Edge 12.10240 Windows 10

    ttttttql

    mmm
    mmm
    离线
    1 年 之前 [2018-10-22 · 20:02]
    Chrome 69.0.3497.100 Windows 10

    tql