← 返回题目列表

AtCoder · qupc2014_g

G. 限制区域

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

問題文

你是一名警察 您所在的地区有多种类型的地块,所有地块都是矩形且与轴线平行。 有一天,恐怖威胁降临。 恐怖主义只针对居住区。 炸弹爆炸的影响区域是圆形的。 我的警察同事很聪明,知道所有炸弹在哪里以及它们的威力有多大。 然而,由于时间不够,他们无法拆除炸弹。 设立禁区,让公民远离。 限制区域应是包含与炸弹爆炸半径重叠的生活区的区域。 由于炸弹的威力可能会有所波动,因此即使生活区与炸弹的爆炸范围接触,该生活区也必须包含在限制区域内。 您的工作是提供设备来标记限制区域。 众所周知,所有炸弹都会同时爆炸,而用于标记禁区的设备是一次性的,所以即使设备被爆炸卷入并被摧毁也没有问题。 使用的设备数量是由外圆周的长度决定的,所以我们要最小化外圆周的长度。 求禁区周长最小时的周长。

入力

输入按以下格式给出。
N M
Cx_0 Cy_0 Cr_0
・
・
Cx_{N-1} Cy_{N-1} Cr_{N-1}
Bx_0 By_0 Bw_0 Bh_0 
・
・
Bx_{M-1} By_{M-1}  Bw_{M-1} Bh_{M-1}
城市以左右为x轴、上下为y轴、上下为正方向来表示。 炸弹数量N,分区数 M, 炸弹地点( Cx,Cy)和爆炸半径Cr 此外,对于每个生活区域,左下顶点 (Bx, By) 和左右长度Bw,顶部和底部长度Bh。

制約

输入时,所有变量均为整数。此外,还满足以下约束条件。 当
  • 1≦N≦100
  • 1≦M≦100
  • -10000≦Cx_i,Cy_i,Bx_i,By_i≦10000
  • 1≦Cr_i,Bh_i,Bw_i≦1000

部分点

如果您正确回答满足以下约束条件的案例,您可以获得80分。
  • N=1
  • M=1
  • -100≦Cx_i,Cy_i,Bx_i,By_i≦100
  • 1≦Cr_i,Bh_i,Bw_i≦100

出力

禁区周长 请在一行中输出l输出的绝对误差为10^{-3}请使用以下内容。 我有一个数字序列

入力例 1

1 1
1 1 1
2 0 2 2

出力例 1

8

入力例 2

1 2
2 3 2
2 0 2 2
1 3 1 1

出力例 2

11.9907

入力例 3

1 2
1 3 1
0 0 3 2
1 5 2 2

出力例 3

10