#P18458. Military Maneuver

Military Maneuver

Military Maneuver

题目描述

二维笛卡尔平面上正在进行一场军事演习。战场上隐藏着 nn 个敌方目标,指挥部已知它们各自的位置。

为了向部队标出全部目标,便于部队将其包围,指挥部将在一个边与坐标轴平行的矩形区域内,均匀随机空投一个信标。该矩形的左下角为 (xl,yl)(x_l,y_l),右上角为 (xr,yr)(x_r,y_r)。

信标落地后,首先从指挥部接收满足 0≤r≤R0\le r\le R 的两个参数 r,Rr,R,然后扫描以落点为共同圆心、内半径为 rr、外半径为 RR 的圆环区域,并标出该区域内的所有目标。圆环的内外边界也包含在扫描范围中。

信标每单位时间只能扫描单位面积。指挥官想知道:为了用指定的圆环区域标出全部目标,信标所需最短扫描时间的期望值是多少?参数可以在信标落地之后根据落点选择。

输入格式

第一行包含四个整数 xl,yl,xr,yrx_l,y_l,x_r,y_r,满足

$$-10000\le x_l,y_l,x_r,y_r\le10000,\qquad x_l<x_r,\quad y_l<y_r,$$

表示空投矩形的左下角和右上角坐标。

第二行包含整数 nn(2≤n≤20002\le n\le2000),表示目标数量。

接下来 nn 行,每行包含两个整数 x,yx,y(−10000≤x,y≤10000-10000\le x,y\le10000),表示一个目标的位置。

保证不存在两个目标位于同一位置。目标不要求位于空投矩形内部。输入没有外层测试组数。

输出格式

输出一个实数,表示信标扫描能够标出全部目标的圆环所需最短时间的期望值。

绝对误差或相对误差不超过 10−610^{-6} 即可。准确地说,设你的输出为 aa,评测答案为 bb,当且仅当

∣a−b∣max⁡(1,∣b∣)≤10−6\frac{|a-b|}{\max(1,|b|)}\le10^{-6}

时,答案被接受。

原样例 1

0 0 2 2
2
3 1
1 3
8.377580409572781970

原样例 2

0 0 2 2
2
5 1
1 3
37.699111843077518863

原样例说明及排版核对

第一个样例中,如果信标落在 (0.5,1.5)(0.5,1.5),可行圆环的最小面积以及最短扫描时间均为 4π4\pi。

信标位于 (0.5,1.5) 时的可行圆环:原题图片

当信标在矩形内均匀随机落下时,最短时间的期望为 8π3\frac{8\pi}{3},与样例输出一致。

原英文 PDF 第 13 页的这一期望数值排成了 3π8\frac{3\pi}{8}。原资料未作修改,这里明确记录更正依据:两点的距离平方之差为 4(x−y)4(x-y),所以最短时间为 4π∣x−y∣4\pi|x-y|;在 [0,2]2[0,2]^2 上 E∣x−y∣=2/3\mathbb E|x-y|=2/3,故真实期望是 8π/38\pi/3。同时,原图指定落点的 4π4\pi 说明也与原定义一致。