#P6472. [thoi2012]森林旅店
[thoi2012]森林旅店
题目描述
树林中的每棵树用一个整数坐标表示,同一坐标至多有一个白蚁穴。初始有 个白蚁穴。接下来处理 次操作,每次加入一个白蚁穴,或者查询某点到当前最近的 个白蚁穴各有多远。
位置 与 的距离定义为
输入格式
第一行四个整数 。接下来 行,每行两个整数,表示初始白蚁穴的坐标。
再接下来 行,每行一个字符及两个整数 。
A x y表示在 加入一个白蚁穴。Q x y表示查询从 到当前最近的 个白蚁穴的距离。
查询时至少有 个白蚁穴。
输出格式
每次查询输出一行 个实数,按距离从小到大排列,以空格分隔,保留小数点后四位。
样例
1 3 1 1
0 0
Q 0 2
A 0 3
Q 0 2
2.0000
1.0000
数据范围
原题数据分为以下十组,每组五个测试点。表中 为上界, 为该组参数。每组有 的数据没有插入操作,所有数据中查询次数不超过 。
| 组别 | ||||
|---|---|---|---|---|
| 1 | 5000 | 2000 | 1 | 1 |
| 2 | 20000 | 10000 | 3 | |
| 3 | 100000 | 5000 | ||
| 4 | 20000 | |||
| 5 | 20000 | 2000 | 2 | 1 |
| 6 | 20000 | 3 | ||
| 7 | 100000 | 5000 | ||
| 8 | 20000 | |||
| 9 | ||||
| 10 |
原 PDF 说明白蚁穴坐标由随机点分别经两个单调函数变换,标注坐标在 。本站现有评测中的初始、插入和查询坐标均为整数,实际范围为 ,实现应支持负坐标和超过 的坐标。