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