solution

Bài toán kim Buffon là một ứng dụng Monte Carlo kinh điển để ước lượng $\pi$: thả ngẫu nhiên một cây kim dài $L$ lên mặt phẳng có các đường kẻ song song cách nhau khoảng $D$ ($L \le D$). Với mỗi lần thả, gọi $y$ là khoảng cách từ tâm kim đến đường kẻ gần nhất ($0 \le y \le D/2$) và $\theta$ là góc hợp bởi kim với đường kẻ ($0 \le \theta \le \pi/2$, đơn vị radian). Kim cắt một đường kẻ khi và chỉ khi:

$y \le \dfrac{L}{2}\sin\theta$

Gọi $\hat p$ là tỉ lệ số lần cắt trên tổng số lần thả $N$. Công thức Buffon cho ước lượng:

$\hat\pi = \dfrac{2L}{D\hat p}$

Dữ liệu $(y_i,\theta_i)$ của từng lần thả được cho sẵn trong đầu vào để bảo đảm kết quả tính toán xác định.

Ví dụ: $L=D=1$, $N=1$, lần thả duy nhất có $y=0,\theta=0$: điều kiện cắt là $0 \le \frac12\sin 0 = 0$, đúng nên cắt. $\hat p = 1$, $\hat\pi = 2\times1/(1\times1)=2.000000$.