作业

圆上相交弦

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

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


圆上相交弦

测试数据下载:

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

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

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

然后按照从小到大排列

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

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

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

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

size()计算总的键的个数

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

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

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

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

最后sum就是答案

此区域的内容仅评论后可见
23 条回应
    azdas 2019-5-21 · 15:28
    Chrome 70.0.3538.67 Linux

    tql

    hcy226 2019-4-8 · 23:31
    Chrome 73.0.3683.75 Windows 10

    nb

    博丽灵梦 2018-12-27 · 21:30
    Chrome 67.0.3396.62 Windows 10

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

      jxtxzzw 2018-12-27 · 22:03
      Chrome 71.0.3578.98 Windows 10

      你好,是的,可以使用线段树直接解决,但是我们的专业课需要要求使用红黑树实现。

    ABC666 2018-12-18 · 22:07
    Chrome 61.0.3163.128 Android 8.0.0 | MI 6

    tql

    czczc 2018-12-10 · 18:40
    Chrome 62.0.3202.94 Windows 10

    tttql

    czc 2018-12-10 · 18:39
    Chrome 62.0.3202.94 Windows 10

    tql

    哈哈黄瓜 2018-12-7 · 17:27
    Firefox 63.0 Windows 10

    zzwtql

    哈哈怪 2018-12-7 · 17:27
    Firefox 63.0 Windows 10

    您tql

    Zoey 2018-12-1 · 19:46
    Chrome 64.0.3282.186 Windows 10

    666

    e 2018-11-2 · 18:52
    Firefox 63.0 Windows 10

    1

    dlgd 2018-10-31 · 22:15
    Chrome 70.0.3538.77 Windows 10

    不会做,听说这里有题解

    deerbean 2018-10-31 · 19:48
    Chrome 70.0.3538.77 Windows 10

    again

    1099 2018-10-30 · 22:09
    Edge 17.17134 Windows 10

    33

    109 2018-10-30 · 18:12
    未知浏览器 未知操作系统

    g g

    Sixuan 2018-10-30 · 13:50
    Chrome 70.0.3538.77 Windows 8

    tql

    deerbean 2018-10-29 · 16:35
    Edge 12.10240 Windows 10

    ttttttql

    mmm 2018-10-22 · 20:02
    Chrome 69.0.3497.100 Windows 10

    tql

    bloodmaster 2018-10-22 · 15:15
    Firefox 62.0 Windows 10

    tql

    k 2018-10-13 · 15:05
    Firefox 61.0 Windows 10

    TQL

    Griffith_Fu 2018-10-8 · 23:24
    Chrome 69.0.3497.100 Windows 10

    tql

    _ 2018-9-28 · 13:28
    Chrome 66.0.3359.181 Windows 10

    retql

    _ 2018-9-28 · 11:39
    Chrome 69.0.3497.100 Windows 10

    tql