作业

圆上相交弦

jxtxzzw · 4月11日 · 2018年 ·

圆上相交弦

测试数据下载:

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

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

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

然后按照从小到大排列

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

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

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

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

size()计算总的键的个数

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

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

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

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

最后sum就是答案

此区域的内容仅评论后可见
20 条回应
  1. 博丽灵梦2018-12-27 · 21:30

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

    • jxtxzzw2018-12-27 · 22:03

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

  2. ABC6662018-12-18 · 22:07

    tql

  3. czczc2018-12-10 · 18:40

    tttql

  4. czc2018-12-10 · 18:39

    tql

  5. 哈哈黄瓜2018-12-7 · 17:27

    zzwtql

  6. 哈哈怪2018-12-7 · 17:27

    您tql

  7. Zoey2018-12-1 · 19:46

    666

  8. e2018-11-2 · 18:52

    1

  9. deerbean2018-10-31 · 19:48

    again

  10. 10992018-10-30 · 22:09

    33

  11. 1092018-10-30 · 18:12

    g g

  12. Sixuan2018-10-30 · 13:50

    tql

  13. deerbean2018-10-29 · 16:35

    ttttttql

  14. mmm2018-10-22 · 20:02

    tql

  15. bloodmaster2018-10-22 · 15:15

    tql

  16. k2018-10-13 · 15:05

    TQL

  17. Griffith_Fu2018-10-8 · 23:24

    tql

  18. _2018-9-28 · 13:28

    retql

  19. _2018-9-28 · 11:39

    tql