← 返回题目列表

Codeforces · 1423/E

E. 5G 天线塔

中文机器翻译题面 查看原题

在与运营商制定了在全国范围内扩展移动网络的战略计划后,政府决定用最后一代5G网络覆盖农村地区。

由于 5G 天线塔将主要建在私人房产区域,政府需要一种简单的方法来查找部分或全部包含在规划建筑区域内的每个房产的土地所有者信息。

规划建筑面积表示为一个边长为 $$$width$$$ 和 $$$height$$$ 的矩形。

每个 5G 天线塔都占据一个圆,其圆心为 $$$(x,y)$$$,半径为 $$$r$$$。

大地测量研究所有一个数据库,其中包含有关每个属性的信息。每个属性都用其标识号和表示为逆时针方向 $$$(x,y)$$$ 点数组的多边形来定义。

您的任务是构建一个 IT 系统,该系统可以处理 $$$(x, y, r)$$$ 类型的查询,其中 $$$(x,y)$$$ 代表圆心,而 $$$r$$$ 代表其半径。 IT系统应返回建造塔楼所需收购的房产总面积,以便政府估算价格。此外,系统应返回这些财产的识别号列表(以便可以联系业主进行土地征用)。

如果天线塔的圆与其相交或接触,则需要获取属性。

输入

第一行包含建筑面积的大小,为双值 $$$width$$$、$$$height$$$ 和一个整数 $$$n$$$ — 数据库中的属性数量。

接下来的 $$$n$$$ 行包含单个属性的描述,其形式为整数 $$$v$$$ ($$$3 \le v \le 40$$$) — 定义属性的点数,以及 $$$2*v$$$ 双数字 — 每个属性点的坐标 $$$(x,y)$$$。 $$$i$$$ ($$$0 \le i \le n-1$$$) 行包含 ID 为 $$$i$$$ 的属性的信息。

下一行包含一个整数 $$$q$$$ — 查询数。

接下来的 $$$q$$$ 行包含双精度值 $$$x$$$、$$$y$$$、$$$r$$$ — 天线圆心 $$$(x, y)$$$ 的坐标及其半径 $$$r$$$。

$$$1 \le n * q \le 10^6$$$

输出

对于每个 $$$q$$$ 查询,您的程序应该输出一行,其中包含需要获取的所有属性的总面积、表示此类属性数量的整数,以及这些属性的 id 列表(以空格字符分隔,任意顺序)。

示例

输入 #1

10 10 3
4 2 2 3 2 3 3 2 3
3 3.5 2 4.5 2 4.5 3
4 7 8 7.5 8.5 8 8 7.5 9
5
2 3.5 0.5
3.3 2 0.4
5 2.5 0.5
7.5 8.5 0.5
3 7 0.5

输出 #1

1.000000 1 0 
1.500000 2 0 1 
0.500000 1 1 
0.250000 1 2 
0.000000 0

注意

您可以假设未覆盖房产(多边形)的土地属于政府所有,因此不需要收购。属性不相互交叉。

用于解决方案检查的精度为 $$$10^{-4}$$$。