#P1264. SCUD Busters

    ID: 265 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>计算几何难度普及/提高-Duke Internet Programming Contest 1991UVA 109

SCUD Busters

题目描述

考虑一个500公里×500公里的平面世界,其中包含多个交战王国。每个王国由高墙隔离,并拥有自己的发电厂。当王国发射导弹击中其他王国时,会摧毁该王国的发电厂。

给定多个王国的坐标(包含发电站和房屋位置)以及导弹落点,编写程序计算所有失去电力供应的王国总面积。

输入格式

  • 多个王国描述,每个王国:
    • 第一行:地点数量N(3≤N≤100)
    • 第二行:发电站坐标
    • 接下来N-1行:房屋坐标
    • N=-1表示王国描述结束
  • 随后是多行导弹落点坐标
  • 所有坐标是0到500的整数

输出格式

  • 一个保留两位小数的浮点数:失去电力的王国总面积

示例输入

输入:
12
3 3
4 6
4 11
4 8
10 6
5 7
6 6
6 3
7 9
10 4
10 9
1 7
5
20 20
20 40
40 20
40 40
30 30
3
10 10
21 10
21 13
-1
5 5
20 12

示例输出

70.50