solution

Phương pháp hit-or-miss dùng Monte Carlo để ước lượng diện tích một miền phẳng: rải $n$ điểm trong một hình chữ nhật bao quanh miền, đếm số điểm rơi vào miền, rồi nhân tỉ lệ đó với diện tích hình chữ nhật.

Cho hình chữ nhật $[-p,p]\times[-q,q]$ và elip $\dfrac{x^2}{p^2}+\dfrac{y^2}{q^2} \le 1$ nằm gọn bên trong. Cho sẵn tọa độ $n$ điểm $(x_i, y_i)$ trong hình chữ nhật (không cần sinh ngẫu nhiên). Gọi $k$ là số điểm thỏa $\dfrac{x_i^2}{p^2}+\dfrac{y_i^2}{q^2} \le 1$ (nằm trong hoặc trên biên elip). Ước lượng Monte Carlo của diện tích elip là:

$\widehat{S} = \dfrac{k}{n}\cdot 4pq$

Diện tích thực của elip là $S = \pi p q$. Hãy in ra $\widehat S$, $S$, và sai số tuyệt đối $|\widehat S - S|$.

Quy ước: nếu $n=0$, quy định $\widehat S = 0$.

Ví dụ: $p=q=1$ (đường tròn đơn vị), $n=4$ điểm (0,0) (2,2) (0.5,0.5) (-2,0): có 2 điểm trong hình tròn $(0,0)$ và $(0.5,0.5)$, nên $\widehat S = 2/4 \cdot 4 = 2.000000$, $S = \pi \approx 3.141593$, sai số $\approx 1.141593$.