蟻本第2版の幾何パートで説明されていますので詳細はそちらに。
多角形や多面体の面積を求める際に使われるテクニックです。被積分関数が2次以下であるという性質を活かして wikipedia: シンプソンの公式 で誤差なく積分することができます。
確率を扱う問題においては点が平面上を動いたり複数の点が線分上を動く場合があります。このような場合にはそれぞれの点が選ばれる確率密度を考えるのが一般的な手法です。そして、その関数を定義域のうち条件が満たされる部分を積分領域に取って積分することで確率を求めます。
2011年の模擬国内予選です。問題はこちら no title
平面上に 2N (N < 100) 個の点がある。これをランダムにえらんだ直線を用いて分割する。これにより N 個ずつに分割される確率を求めよ。
2つの点が独立に一様に選ばれるので、同時分布は一様分布になります。従って積分領域の面積を求めればよいことになります。
片方の点を固定したときの偏角ソートを考えるとよいです。この時のもう片方の取りうる部分の長さ (スライドの y2) を積分します。被積分関数が変化する点で区間を分割し、各区間は y2 が線型に変化することから台形公式で誤差なく積分できます。区間の分割点を洗い出すには偏角ソートの順番が入れ替わる部分である2つの点を結んで得た直線との交点と、y2 の区間のうちの片方が端に到達する部分である1つの点と長方形の頂点を結んで得た直線との交点を調べれば十分です。
2013年の夏合宿4日目が類題です。問題はこちら。 H: Gravity Point - Japan Alumni Group Summer Camp 2013 Day 4 | AtCoder