答えが \(z\) 以上になる確率を \(f(z)\) と置くと，\(f\) を積分することで期待値は求まります． そこで，\(f(z)\) を求めることを考えます．

\(z\) を固定した場合の問題は，次のようにして解けます． まず，\(N\) 個の区間 \([x_i-(i-1)z,x_{i+1}-(i-1)z]\) を考えます． すると，各区間から一様ランダムに選んだ実数 \(y_i\) が，\(y_1<y_2<\ldots<y_N\) を満たす確率を求める問題になります． 区間の端の座標をソートし，\(v_1<v_2<\ldots<v_{2N}\) とおきます． すると，次のようなDPを考えることができます．

• \(dp[i][j][k]=y_i\) までの値を決めており，\(y_{i-k}< v_j < y_{i-k+1} < \ldots < y_i \leq v_{j+1}\) である確率．

このようにすると，\(dp\) の遷移を書くことができます． 重要な遷移は \(dp[i][j][k] \rightarrow dp[i+1][j][k+1]\) で，この場合は，\(y_{i+1}\) が \([v_j,v_{j+1}]\) に含まれる確率に，更に \(1/(k+1)\) をかけた重みで遷移します．この \(1/(k+1)\) の項は，\(k\) 個の値が昇順である確率が \(k+1\) 個の値が昇順である確率に変わることに対応します．

このDPを行うことで \(O(poly(N))\) で \(z\) が固定された場合の答えが求まりました．

\(z\) を動かすことを考えます． \(v_i\) の値は，すべて \(-az+b\) の形で書ける値です． そして，上のDPの答えは，\(v_i\) の多項式になっています． 結局，\((v_1,v_2,\ldots,v_{2N})\) の値が \(z\) の一次式として同じならば，DP の答えは同じ \(z\) の多項式です． よって，\(z\) を動かす場合は，\(v_i\) の値が変化する（つまり \(z\) の一次式の大小関係が入れ替わる）ところに注目して，変化しない部分は，上の DPを行えばよいです．ここで，DP の値を \(z\) の多項式として保持するか，いくつかの \(z\) で評価して多項式補間を行えば，最後に \(f(z)\) の積分を行えます．

\(v_i\) の値の変化は \(O(N^2)\) 回しかおきないことから，結局，この問題は \(O(poly(N))\) で解けることになります． 想定解は \(O(N^6)\) ですが，定数倍が悪すぎなければ \(O(N^7)\) なども AC します．