最短路，自适应$Simpson$积分。

看了别人的题解才知道有个东西叫自适应$Simpson$积分。

有这样一个积分公式：$\int_a^b {f(x)dx}  \approx \frac{

{b - a}}{6}\left[ {f(a) + 4f\left( {\frac{

{a + b}}{2}} \right) + f(b)} \right]$。这个东西用于计算不方便直接积分的时候的近似积分。

由于直接套公式会与实际有很大偏差，有一个改进：

要求$[L,R]$的积分，先令$m = \frac{

{L + R}}{2}$，根据上面的公式，求出$[L,R]$的公式值${s_0}$，以及$[L,m]$的公式值${s_1}$，$[m,R]$的公式值${s_2}$。

如果${s_0}$与${s_1} + {s_2}$很接近，那么可以认为$[L,R]$的积分就是${s_0}$；否则进行递归，分别求$[L,m]$的积分和$[m,R]$的积分。

知道了这个东西之后，这题就变成水题了......

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include