#P6879. banana

    ID: 6710 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000省选/NOI-线段树分治活跃时间区间挂树扫描线凸包叉积消除被支配候选合并有序结果高精度乘法二分查找定点数十进制舍入

banana

题目描述

维护一个初始为空的平面点集,支持加入、删除和询问。

对于询问点 Q=(x,y)Q=(x,y),从 QQ 向 yy 轴负方向发出一条射线。求射线顺时针旋转后首次碰到当前点集中某个点所需的最小角度,只考虑横坐标不大于 xx 的点。若不存在这样的点,角度为 π\pi。若 QQ 本身属于点集,射线从起点已经碰到它,角度为 00。

设全部询问得到的角度的最小值为 zz。整个输入只输出一次 cos⁡z\cos z。

输入格式

第一行一个整数,表示测试集编号。

第二行两个整数 N,CN,C,分别表示操作数与输出的小数位数。接下来 NN 行,每行是以下一种操作。

  • 1 x y:将点 (x,y)(x,y) 加入点集。
  • 2 x y:从点集中删除点 (x,y)(x,y)。保证要删除的点存在。
  • 3 x y:以点 (x,y)(x,y) 为起点进行询问。

输出格式

输出一行,包含一个实数 cos⁡z\cos z,四舍五入后保留恰好 CC 位小数。输出须与标准输出一致。

保证准确值与按要求舍入后的值之差的绝对值不大于 4×10−(C+1)4\times10^{-(C+1)}。

样例

0
3 6
1 2 3
3 3 4
3 3 5
0.894427

数据范围

1≤N≤1061\le N\le10^6,C∈{6,18,30}C\in\{6,18,30\}。对所有加入和询问操作,∣x∣,∣y∣≤1018|x|,|y|\le10^{18}。至少有一次询问。

原测试集编号 NN 上限 CC 原赛分值 额外条件
1 2 30 20
2 10510^5 18 15
3 5×1055\times10^5 6 23 无删除操作
4 10610^6 18 18 操作类型单调不降
5 21
6 30 3

范致远原题 PDF。上表为原题分档。本站按原题题意、样例与评测答案统一为一行汇总输出。