金融风暴

时间限制:20s      空间限制:256MB

题目描述

在这次金融危机爆发之前,小L就有预感。她准确地预测到了爆发地点以及扩散的形式和速度。因此,金融危机爆发时,小L的很多好友都马上来找她帮忙,希望尽可能晚的遭到金融风暴的影响。
为了简化问题,我们将地球变成二维平面(坐标值非负。最左与最右,最上与最下不可直接互达)。每个整点都为一个城市。在第0时刻只有N个金融中心爆发了金融风暴,第i个金融中心是坐标(xi,yi)。金融风暴扩散的方式是以金融中心为圆心做均匀的圆扩散。即世界上每个城市受到第i个金融风暴影响的时间为这个城市与这场风暴中心(xi,yi)的欧几里德距离。注意,地球外没有城市,金融危机也不会爆发到地球外面XD
L希望你写个程序来帮帮她。
现有t个好友希望小L帮忙,因为各个人所在的不同地方以及国家大小原因。你需要告诉她与第i个好友所在的(pi,qi)横纵坐标距离不超过si的所有城市(即{(a,b)|max{|a-pi||b-qi|}<=si})中,最晚遭受金融风暴影响的城市开始爆发金融危机的时间(为严格定义,如果需要覆盖到地球外的区域,则输出-1)。
 


输入格式

   第一行两个数,地图大小w,h
   第二行一个数N,金融中心坐标
   接下来N行,(xi,yi)   0<=xi<=w, 0<=yi<=h
   N+3行一个数t,为询问数
   接下来t行,每行三个数,(pi,qi)表示好友的坐标,si如题中描述意义。
 


输出格式

   t行,每行一个数time如题中描述。(保留3位小数)
 


样例输入

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

样例输出

    0.000
    1.414
    -1
 
【数据说明】
 20% 0<=w,h<=100
1<=N,t<=1000
60% 1<=t<=200000
100% 0<=w,h<=1000
1<=N,t<=1000000

提示

没有写明提示


题目来源

没有写明来源