#P18458. Military Maneuver
Military Maneuver
Military Maneuver
题目描述
二维笛卡尔平面上正在进行一场军事演习。战场上隐藏着 个敌方目标,指挥部已知它们各自的位置。
为了向部队标出全部目标,便于部队将其包围,指挥部将在一个边与坐标轴平行的矩形区域内,均匀随机空投一个信标。该矩形的左下角为 ,右上角为 。
信标落地后,首先从指挥部接收满足 的两个参数 ,然后扫描以落点为共同圆心、内半径为 、外半径为 的圆环区域,并标出该区域内的所有目标。圆环的内外边界也包含在扫描范围中。
信标每单位时间只能扫描单位面积。指挥官想知道:为了用指定的圆环区域标出全部目标,信标所需最短扫描时间的期望值是多少?参数可以在信标落地之后根据落点选择。
输入格式
第一行包含四个整数 ,满足
$$-10000\le x_l,y_l,x_r,y_r\le10000,\qquad x_l<x_r,\quad y_l<y_r,$$表示空投矩形的左下角和右上角坐标。
第二行包含整数 (),表示目标数量。
接下来 行,每行包含两个整数 (),表示一个目标的位置。
保证不存在两个目标位于同一位置。目标不要求位于空投矩形内部。输入没有外层测试组数。
输出格式
输出一个实数,表示信标扫描能够标出全部目标的圆环所需最短时间的期望值。
绝对误差或相对误差不超过 即可。准确地说,设你的输出为 ,评测答案为 ,当且仅当
时,答案被接受。
原样例 1
0 0 2 2
2
3 1
1 3
8.377580409572781970
原样例 2
0 0 2 2
2
5 1
1 3
37.699111843077518863
原样例说明及排版核对
第一个样例中,如果信标落在 ,可行圆环的最小面积以及最短扫描时间均为 。

当信标在矩形内均匀随机落下时,最短时间的期望为 ,与样例输出一致。
原英文 PDF 第 13 页的这一期望数值排成了 。原资料未作修改,这里明确记录更正依据:两点的距离平方之差为 ,所以最短时间为 ;在 上 ,故真实期望是 。同时,原图指定落点的 说明也与原定义一致。