5G Antenna Towers

题意翻译

### 题目描述 给定平面上 $n$ 个**互不相交**的多边形，编号从 $0$ 到 $n-1$。每组询问给出一个圆的圆心坐标和半径，要求回答与这个圆相交（一个点也算）的所有多边形的面积之和及它们的编号。 ### 输入格式 第一行三个数，两个浮点数 $width,height$， 表示平面的宽和高。一个整数 $n$ 表示多边形的数量。 接下来 $n$ 行，每行是一个多边形的信息，第$i\ (0\leq i\leq n-1)$行包含了编号为 $i$ 的多边形的信息。每行第一个整数 $v\ (3\leq v\leq40)$ 表示多边形的点数，接下来 $2\times v$ 个浮点数，每两个数 $(x,y)$ 代表多边形的一个点的坐标，将按**逆时针**的顺序给出。 接下来一行，输入一个整数 $q$ ，表示询问的个数。 接下来 $q$ 行，每行是一个圆的信息。前两个浮点数 $(x,y)$ 代表圆心的坐标，第三个浮点数 $r$ 代表半径。 保证 $1\leq n\times q\leq 10^6$。 ### 输出格式 对于每一组询问，输出一行。输出一个浮点数代表与这个圆相交（一个点也算）的所有多边形的面积之和。接下来输出一个整数，代表多边形的个数，接下来按任意顺序输出若干个整数，代表它们的编号。 所有数字之间以一个空格分开，你的答案应该与标准答案之差小于 $10^{-4}$。 ### 说明/提示 对于样例，易知多边形 $0,1,2$ 的面积分别为 $1,0.5,0.25$。对于第二组询问，圆与多边形 $0,1$ 相交，因此面积之和为 $1+0.5=1.5$。

题目描述

After making a strategic plan with carriers for expansion of mobile network throughout the whole country, the government decided to cover rural areas with the last generation of 5G network. Since 5G antenna towers will be built in the area of mainly private properties, the government needs an easy way to find information about landowners for each property partially or fully contained in the planned building area. The planned building area is represented as a rectangle with sides $ width $ and $ height $ . Every 5G antenna tower occupies a circle with a center in $ (x,y) $ and radius $ r $ . There is a database of Geodetic Institute containing information about each property. Each property is defined with its identification number and polygon represented as an array of $ (x,y) $ points in the counter-clockwise direction. Your task is to build an IT system which can handle queries of type $ (x, y, r) $ in which $ (x,y) $ represents a circle center, while $ r $ represents its radius. The IT system should return the total area of properties that need to be acquired for the building of a tower so that the government can estimate the price. Furthermore, the system should return a list of identification numbers of these properties (so that the owners can be contacted for land acquisition). A property needs to be acquired if the circle of the antenna tower is intersecting or touching it.

输入输出格式

输入格式

The first line contains the size of the building area as double values $ width $ , $ height $ , and an integer $ n $ — the number of properties in the database. Each of the next $ n $ lines contains the description of a single property in the form of an integer number $ v $ ( $ 3 \le v \le 40 $ ) — the number of points that define a property, as well as $ 2*v $ double numbers — the coordinates $ (x,y) $ of each property point. Line $ i $ ( $ 0 \le i \le n-1 $ ) contains the information for property with id $ i $ . The next line contains an integer $ q $ — the number of queries. Each of the next $ q $ lines contains double values $ x $ , $ y $ , $ r $ — the coordinates of an antenna circle center $ (x, y) $ and its radius $ r $ . $ 1 \le n * q \le 10^6 $

输出格式

For each of the $ q $ queries, your program should output a line containing the total area of all the properties that need to be acquired, an integer representing the number of such properties, as well as the list of ids of these properties (separated by blank characters, arbitrary order).

输入输出样例

输入样例 #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

说明

You can assume that the land not covered with properties (polygons) is under the government's ownership and therefore doesn't need to be acquired. Properties do not intersect with each other. Precision being used for solution checking is $ 10^{-4} $ .