bzoj#P2646. neerc2011 flight

neerc2011 flight

题目描述

NN 个抛物线 (只会完整地存在在第一象限,不在第一象限的部分不需考虑,如图) 。

pic1

询问 MM 次,每次询问第 ii 到第 jj 个抛物线在 [l,r][l,r]xx 坐标区间上的最小值。

输入格式

所有输入均为整数。
第一行 NN 一个整数。
接下来 NN 行,每行 p,x,yp,x,y 表示抛物线左边界的 xx 坐标,顶点的 x,yx,y 坐标区间上的最小值。
接下来 MM 一个整数。
接下来 MM 行,每行 i,j,l,ri,j,l,r 如题意所示。

输出格式

MM 行每行一个实数,表示第 MM 次询问的答案,误差 <14<1^{-4} 即可。

2
10 30 10
20 30 30
4
1 2 0 11
1 2 20 25
1 2 25 35
1 2 45 100
0.975
22.5
30.0
4.375
 

数据规模与约定

对于 100%100\% 的数据,1n5×1041 \leq n \leq 5 \times 10^40p<x5×1040 \leq p < x \leq 5 \times 10^40<y500 < y \leq 501m2×1041 \leq m \leq 2 \times 10^40lr5×1040 \leq l \leq r \leq 5 \times 10^41abn1 \leq a \leq b \leq n

题目来源

鸣谢Kac