← 返回题目列表

Codeforces · 44/F

F. 伯兰涂色

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

猴子 Anfisa 对文字处理程序感到失望,因为它们不足以反映她的所有情绪,这就是她决定改用图形编辑器的原因。打开BerPaint后,她看到了一个宽×高大小的白色矩形,可以在上面绘画。首先,Anfisa 学会了如何操作用于绘制线段的绘图工具,并快速在该矩形上绘制一定数量的黑色线段。生成的图片对 Anfisa 来说似乎不够明亮,这就是为什么她将注意力转向“填充”工具,该工具用于在矩形上找到一个点来绘制并选择颜色,之后所有与其包含的点颜色相同的区域都完全绘制为所选颜色。涂了几次填充后,安菲萨彻底表达了自己的情绪,然后停止了绘画。您的任务是通过有关绘制的段和应用的填充的信息来找出每种颜色在所有填充后绘制该颜色的区域的总面积。

输入

第一输入行有两个整数 W 和 H (3 ≤ W, H ≤ 104) — 最初白色矩形绘画区域的大小。第二行包含整数 n — 黑色段的数量 (0 ≤ n ≤ 100)。接下来的 n 行描述了线段本身,每个线段由其端点 x1、y1、x2、y2 的坐标给出(0 < x1、x2 < W、0 < y1、y2 < H)。所有段的长度都不为零。下一行包含预设的填充数 m (0 ≤ m ≤ 100)。接下来的 m 行中的每一行都以“x y color”的形式定义填充操作,其中 (x, y) 是所选点的坐标 (0 < x < W, 0 < y < H),而 color — 长度为 1 到 15 个符号的小写拉丁字母行,确定颜色。输入中给出的所有坐标都是整数。最初,矩形的颜色为“白色”,而线段的颜色为“黑色”。

输出

对于最终图片中出现的每种颜色,在单行上打印该颜色的名称以及绘制该颜色的区域的总面积,精度为 10 - 6。以任何顺序打印颜色。

示例

输入 #1

4 5
6
1 1 1 3
1 3 3 3
3 3 3 1
3 1 1 1
1 3 3 1
1 1 3 3
2
2 1 red
2 2 blue

输出 #1

blue 0.00000000
white 20.00000000

输入 #2

5 5
5
1 1 2 2
2 2 4 2
4 2 4 4
4 4 2 4
2 4 2 2
2
3 3 black
3 3 green

输出 #2

green 4.00000000
white 21.00000000

输入 #3

7 4
9
1 2 2 3
2 3 3 2
3 2 2 1
2 1 1 2
3 2 4 2
4 2 5 3
5 3 6 2
6 2 5 1
5 1 4 2
2
2 2 black
2 2 red

输出 #3

red 2.00000000
white 26.00000000

注意

最初,如果任何选定的点位于该段上,则 Anfisa 绘制的黑色段也可以涂上颜色。这些线段的面积等于 0。这就是为什么如果在最终图片中只有部分线段被涂上了某种颜色,那么涂有颜色的面积就等于 0。