CF1218B.Guarding warehouses

NOI/NOI+/CTSC

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Bob Bubblestrong just got a new job as security guard. Bob is now responsible for safety of a collection of warehouses, each containing the most valuable Bubble Cup assets - the high-quality bubbles. His task is to detect thieves inside the warehouses and call the police.

Looking from the sky, each warehouse has a shape of a convex polygon. Walls of no two warehouses intersect, and of course, none of the warehouses is built inside of another warehouse.

Little did the Bubble Cup bosses know how lazy Bob is and that he enjoys watching soap operas (he heard they are full of bubbles) from the coziness of his office. Instead of going from one warehouse to another to check if warehouses are secured, the plan Bob has is to monitor all the warehouses from the comfort of his office using the special X-ray goggles. The goggles have an infinite range, so a thief in any of the warehouses could easily be spotted.

However, the goggles promptly broke and the X-rays are now strong only enough to let Bob see through a single wall. Now, Bob would really appreciate if you could help him find out what is the total area inside of the warehouses monitored by the broken goggles, so that he could know how much area of the warehouses he needs to monitor in person.

鲍勃·巴布尔斯特朗刚刚获得了一份新工作,担任保安。鲍勃现在负责一组仓库的安全,而每个仓库中都存放着泡泡杯(Bubble Cup)最宝贵的资产——高品质的泡泡。他的任务是检测仓库内部的窃贼,并及时报警。

从空中俯瞰,每个仓库的形状均为一个凸多边形。任意两个仓库的墙壁互不相交,且显然,没有任何一个仓库建在另一个仓库内部。

泡泡杯的老板们万万没想到鲍勃有多么懒惰——他喜欢舒舒服服地待在自己的办公室里追 soap opera(肥皂剧)(他听说肥皂剧中充满了泡泡)。因此,他并不打算亲自逐一巡查各个仓库以确认其安全性;相反,他计划利用一副特制的 X 射线护目镜,在办公室内远程监控所有仓库。该护目镜原本具有无限穿透范围,因此任何仓库内的窃贼都可被轻易发现。

然而,这副护目镜却突然损坏了,如今 X 射线强度仅足以让鲍勃看穿单面墙壁。现在,鲍勃非常希望你能帮他计算出:在当前损坏状态下,X 射线护目镜所能监控到的、位于所有仓库内部的总面积是多少?这样他便能知道,自己还需亲自巡查的仓库面积有多大。

输入格式

The first line contains one integer NN (11 ≤\leq NN ≤\leq 10410^4) – the number of warehouses.

The next NN lines describe the warehouses.

The first number of the line is integer cic_i (33 ≤\leq cic_i ≤\leq 10410^4) – the number corners in the ithi^{th} warehouse, followed by cic_i pairs of integers. The jthj^{th} pair is (xj,yj)(x_j, y_j) – the coordinates of the jthj^{th} corner (∣xj∣|x_j|, ∣yj∣|y_j| ≤\leq 3∗1043 * 10^4). The corners are listed in the clockwise order. The total number of corners in all the warehouses is at most 5∗1045 * 10^4.

Bob's office is positioned at the point with coordinates (0,0)(0, 0). The office is not contained within any of the warehouses.

第一行包含一个整数 NN(1≤N≤1041 \leq N \leq 10^4)——仓库的数量。

接下来的 NN 行描述各个仓库。

每行的第一个数为整数 cic_i(3≤ci≤1043 \leq c_i \leq 10^4)——第 ii 个仓库的顶点数,随后是 cic_i 对整数。第 jj 对整数为 (xj,yj)(x_j, y_j)——第 jj 个顶点的坐标(满足 ∣xj∣,∣yj∣≤3×104|x_j|, |y_j| \leq 3 \times 10^4)。所有顶点按顺时针顺序给出。所有仓库的顶点总数不超过 5×1045 \times 10^4。

Bob 的办公室位于坐标为 (0,0)(0, 0) 的点处。该办公室不位于任何一个仓库内部。

输出格式

Print a single line containing a single decimal number accurate to at least four decimal places – the total area of the warehouses Bob can monitor using the broken X-ray goggles.

输出一行,包含一个十进制数,精确到至少小数点后四位——即 Bob 使用损坏的 X 射线护目镜所能监控的仓库总面积。

输入输出样例

  • 输入#1

    5
    4 1 1 1 3 3 3 3 1
    4 4 3 6 2 6 0 4 0
    6 -5 3 -4 4 -3 4 -2 3 -3 2 -4 2
    3 0 -1 1 -3 -1 -3
    4 1 -4 1 -6 -1 -6 -1 -4

    输出#1

    13.333333333333

说明/提示

Areas monitored by the X-ray goggles are colored green and areas not monitored by the goggles are colored red.

The warehouses ABCDABCD, IJKIJK and LMNOPQLMNOPQ are completely monitored using the googles.

The warehouse EFGHEFGH is partially monitored using the goggles: part EFWEFW is not monitored because to monitor each point inside it, the X-rays must go through two walls of warehouse ABCDABCD.

The warehouse RUTSRUTS is not monitored from the Bob's office, because there are two walls of the warehouse IJKIJK between Bob's office and each point in RUTSRUTS.

The total area monitored by the goggles is PP = PABCDP_{ABCD} + PFGHWP_{FGHW} + PIJKP_{IJK} + PLMNOPQP_{LMNOPQ} = 44 + 3.3333333333333.333333333333 + 22 + 44 = 13.33333333333313.333333333333.

X光护目镜监控的区域为绿色,未被护目镜监控的区域为红色。

仓库 ABCDABCD、IJKIJK 和 LMNOPQLMNOPQ 均被护目镜完全监控。

仓库 EFGHEFGH 仅被护目镜部分监控:其中区域 EFWEFW 未被监控,因为要监控该区域内任意一点,X射线必须穿过仓库 ABCDABCD 的两堵墙。

仓库 RUTSRUTS 无法从鲍勃办公室被监控,因为鲍勃办公室与 RUTSRUTS 内任意一点之间均隔着仓库 IJKIJK 的两堵墙。

护目镜监控的总面积为 P=PABCD+PFGHW+PIJK+PLMNOPQ=4+3.333333333333+2+4=13.333333333333P = P_{ABCD} + P_{FGHW} + P_{IJK} + P_{LMNOPQ} = 4 + 3.333333333333 + 2 + 4 = 13.333333333333。

输入解题思路,AI测评打分。不知道怎么写?

首页