[CTSC2009] 魔幻花园
题目描述
魔法师栋栋有一个美丽的魔幻花园,在花园里,栋栋种满各式各样的魔幻植物,花园里一年四季都开满着姹紫嫣红的鲜花。栋栋的朋友们都特别喜欢来花园里玩。
花园的浇灌系统是由栋栋特别设计的,栋栋用魔法在花园上空变出了$n$个喷头,这些喷头都连接着附近的圣水河。浇灌的时候,所有的喷头一起喷出一道道水流,水流在空中划出一道道美丽的弧线,最终正好浇灌到n棵最缺水的魔幻植物上。
![喷头](https://cdn.luogu.com.cn/upload/pic/18045.png)
栋栋把每个喷头都设在同一水平高度$h$。所有的喷头都是水平放置的,当水流从喷头喷出时,只有水平的速度(每个喷头的水平速度不一定相同)。魔幻花园里没有风,空气阻力可以忽略。所以在重力的影响下(魔幻花园的重力加速度为$g$),水流的轨迹是一条完美的抛物线。空间上的任意点都最多被三个喷头喷到,两条水流相交不会影响各自的轨迹。
近些年来魔幻花园附近新建了许多工厂,圣水河受到了污染,栋栋不想受污染的水影响到他的花园,所以他要使用魔法先净化一下浇灌的水。栋栋的魔法只能净化从喷头喷出来的水,他可以施魔法在空中的一个水平面形成一个凸多边形的滤水层,所有通过滤水层的水都会被净化,施这个魔法需要的能量和滤水层的面积成正比,每平方米滤水层需要$1$单位的魔法能量。栋栋想净化所有的水,他最少需要多少能量呢?
为了更好的描述问题,栋栋在花园建立起了一个三维的直角坐标系,以花园的西北角为坐标轴的原点,从原点向东是$x$轴的正方向,向南是$y$轴的正方向,向上是$z$轴的正方向。这样第$i$个喷头的位置可以用$(x_i,y_i,h)$来表示,而第$j$棵魔幻植物的位置可以用$(x_j',y_j',0)$来表示。
输入输出格式
输入格式
输入文件*garden.in*第一行为两个实数$h, g$,表示喷头的高度和魔幻花园的重力加速度。第二行为整数$n$,表示有多少个喷头。
接下来$n$行,每行四个整数$x_i, y_i, x_i', y_i'$,整数间使用一个空格分隔。表示第i个喷头的坐标是$(x_i, y_i, h)$,它喷出的水正好浇灌到了$(x_i', y_i', 0)$位置的魔幻植物上。
输出格式
输出文件*garden.out*仅有一个实数,表示栋栋最少需要的能量,至少精确到小数点后3位。
输入输出样例
输入样例 #1
36 2
3
99 100 105 100
101 100 95 100
100 99 100 105
输出样例 #1
0.000
输入样例 #2
10 9.8
3
0 0 0 0
1 0 100 0
0 50 0 1
输出样例 #2
25.0000
说明
**【样例说明1】**
在高度为$35$的地方施魔法,此时所有的水流正好汇合到$(100, 100, 35)$这点,所以需要的能量为$0$。
**【样例说明2】**
在高度为$10$的地方(即喷头处)施魔法,魔法形成一个直角三角形,三个点的坐标分别为:$(0,0,10), (1,0,10), (0,50,10)$,面积为$25.000$,所以需要的魔法能量也为$25.000$。
**【评分标准】**
对于每个测试点,如果你的答案与标准答案的差不超过$0.001$,则得到该测试点的全部分数;如果你的答案与标准答案的差超过$0.001$但不超过$0.002$,则得到50%的分数;否则得0分。
**【数据规模】**
对于20%的数据,$1 \leq n \leq 10$
对于50%的数据,$1 \leq n \leq 50$
对于100%的数据,$1 \leq n \leq 100$
$0 < h \leq 10000.0$
$0 < g \leq 100.0$
$0 \leq x_i, y_i, x_i', y_i' \leq 1000$
**【提示】**
水从喷头喷出到地面的过程可以看成一个平抛运动。平抛运动可以分解为向
水平方向和竖直方向的两个分运动:
令$L = (x_i - x_i')^2 + (y_i - y_i')^2$,则
初始速度$v_0 = \sqrt{\frac{Lg}{2h}}$
$t$时刻的水平分速度:$v_{\text{平}}(t) = v_0$
$t$时刻的竖直分速度:$v_{\text{竖}}(t) = gt$
$t$时刻的速度:$v(t) = \sqrt{v_{\text{平}}^2(t) + v_{\text{竖}}^2(t)}$