翻译
查看原帖
翻译
333580
Zwaire楼主2022/1/20 07:32

题目描述

有些问题很难解决,但简化后很容易解决。考虑到一个 500 公里 × 500 公里的前哥伦布平坦世界,而不是处理建造地球模型(一个稍扁球形)的困难。

在这个问题中使用的模型中,世界由几个交战的王国组成。虽然国家之间好战,但世界人民是严格的孤立主义者。每一个王国都被一堵高(但薄)的墙所包围,这堵墙既保护王国,又隔离王国。为了避免争夺电力,每个王国都有自己的发电厂。

当战争的欲望变得太强烈时,一个王国的人民经常向其他王国发射导弹。每一枚导弹降落在一个王国内即会摧毁该王国的发电厂(没有生命损失)。

给定多个王国的坐标位置(通过指定一个王国中房屋的位置和发电厂的位置)和导弹着陆的位置,您需要编写一个程序,确定导弹攻击后所有没有电力的王国的总面积。

在这个问题的世界中,王国不会重叠。此外,每个王国周围的墙被认为是零厚度的。王国周围的墙是最小的周长,完全包围了构成王国的所有房屋和发电站;王国的面积是由最小周长薄壁所包围的区域。

每个王国只有一个发电站。

王国之间可能有空白。

输入格式

输入是一系列王国规格,然后是一系列导弹着陆位置。

在一行上输入一个数字 NN (3N100)(3 \le N \le 100) ,表示该王国的领地数量。下一行包含发电站的 x 和 y 坐标,后跟 N − 1 行 x,y 对,表示该发电站所服务领地的位置。输入 -1 表示不再有王国。数据保证至少有一个王国。

在最后一个王国输入完毕之后,将是一个或多个导弹攻击的坐标,指示导弹着陆的位置。你要处理导弹攻击直到输入的末尾。

使用 500 km × 500 km 网格上的坐标以公里为单位指定位置。所有坐标都是 0 到 500 之间的整数(包括 0 和 500)。坐标指定为一对整数,在单行上用空格分隔。输入文件将由多达 20 个王国组成,然后是任意数量的导弹攻击。

输出格式

输出由一个数字组成,代表在所有导弹攻击处理完毕后所有断电王国的总面积。数字应保留两位小数。

提示:

您可能会发现以下公式有用,也可能不会。给定顶点 v0,v1,,vnv_0,v_1,\cdots, v_n 的多边形,使得 v0=vn v_0=v_n,多边形的有符号区域由以下公式给出:

a=12i=1n(xi1yi)(xiyi1)a= \frac1{2}\sum^n_{i=1}(x_{i-1}y_i)-(x_iy_{i-1})

公式中,viv_i 坐标为 (xi,yi)(x_i, y_i), 当 i=0n1i=0\cdots n-1 时,多边形的边从 viv_ivi+1v_{i+1}。如果描述多边形的点按逆时针方向给出,则 a 的值为正值,如果多边形的点按顺时针方向列出,则 a 的值为负值。

## 题目描述

有些问题很难解决,但简化后很容易解决。考虑到一个 500 公里 × 500 公里的前哥伦布平坦世界,而不是处理建造地球模型(一个稍扁球形)的困难。

在这个问题中使用的模型中,世界由几个交战的王国组成。虽然国家之间好战,但世界人民是严格的孤立主义者。每一个王国都被一堵高(但薄)的墙所包围,这堵墙既保护王国,又隔离王国。为了避免争夺电力,每个王国都有自己的发电厂。


当战争的欲望变得太强烈时,一个王国的人民经常向其他王国发射导弹。每一枚导弹降落在一个王国内即会摧毁该王国的发电厂(没有生命损失)。

给定多个王国的坐标位置(通过指定一个王国中房屋的位置和发电厂的位置)和导弹着陆的位置,您需要编写一个程序,确定导弹攻击后所有没有电力的王国的总面积。

在这个问题的世界中,王国不会重叠。此外,每个王国周围的墙被认为是零厚度的。王国周围的墙是最小的周长,完全包围了构成王国的所有房屋和发电站;王国的面积是由最小周长薄壁所包围的区域。

每个王国只有一个发电站。

王国之间可能有空白。

## 输入格式

输入是一系列王国规格,然后是一系列导弹着陆位置。


在一行上输入一个数字 $N$ $(3 \le N \le 100)$ ,表示该王国的领地数量。下一行包含发电站的 x 和 y 坐标,后跟 N − 1 行 x,y 对,表示该发电站所服务领地的位置。输入 -1 表示不再有王国。数据保证至少有一个王国。

在最后一个王国输入完毕之后,将是一个或多个导弹攻击的坐标,指示导弹着陆的位置。你要处理导弹攻击直到输入的末尾。

使用 500 km × 500 km 网格上的坐标以公里为单位指定位置。所有坐标都是 0 到 500 之间的整数(包括 0 和 500)。坐标指定为一对整数,在单行上用空格分隔。输入文件将由多达 20 个王国组成,然后是任意数量的导弹攻击。

## 输出格式

输出由一个数字组成,代表在所有导弹攻击处理完毕后所有断电王国的总面积。数字应保留两位小数。

## 提示:
您可能会发现以下公式有用,也可能不会。给定顶点  $v_0,v_1,\cdots, v_n$ 的多边形,使得 $ v_0=v_n$,多边形的有符号区域由以下公式给出:

$$a= \frac1{2}\sum^n_{i=1}(x_{i-1}y_i)-(x_iy_{i-1})$$

公式中,$v_i$ 坐标为 $(x_i, y_i)$, 当 $i=0\cdots n-1$ 时,多边形的边从 $v_i$ 到 $v_{i+1}$。如果描述多边形的点按逆时针方向给出,则 a 的值为正值,如果多边形的点按顺时针方向列出,则 a 的值为负值。
2022/1/20 07:32
加载中...