Visits: 861

圆上相交弦

测试数据下载：

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

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

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

然后按照从小到大排列

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

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

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

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

size()计算总的键的个数

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

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

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

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

最后sum就是答案