题目描述
Math is important!! Many students failed in 2+2’s mathematical test, so let’s AC this problem to mourn for our lost youth..
Look at this sample picture:
An ellipse in a plane centered on point $O$. The $L, R$ lines will be vertical through the $X$-axis. The problem is calculating the blue intersection area. But calculating the intersection area is dull, so I have to turn to you, a talent of programmer. Your task is telling me the result of calculation. (defined $\pi=3.14159265$, the area of an ellipse $A=\pi ab$)
题意概述
给定$a, b, l, r$,求椭圆${x^2 \over a^2}+{y^2 \over b^2}=1$在直线$x=l$与$x=r$之间的面积。
数据范围:$-a \le l \le r \le a$。
算法分析
这是一个不规则图形,无法直接计算,但我们可以用积分来求面积。设$f(n)$表示直线$x=n$与椭圆的两个交点之间的距离。
根据辛普森公式
$$
\int_a^b f(x) \, {\rm d}x \approx {b-a \over 6} \left(f(a)+4f\left({a+b \over 2}\right)+f(b)\right)
$$
但这样的精度并不是很高。考虑二分,令
$$g(l, r)=\int_l^r f(x) \, {\rm d}x, \; h(l, r)={r-l \over 6} \left(f(l)+4f\left({l+r \over 2}\right)+f(r)\right)$$
当$h(l, r)$与$h\left(l, {l+r \over 2}\right)+h\left({l+r \over 2}, r\right)$的差足够小时,令
$$g(l, r)=h(l, r)$$
否则
$$g(l, r)=g\left(l, {l+r \over 2}\right)+g\left({l+r \over 2}, r\right)$$
这样就可以达到精度要求。
代码
/* * Today is what happened to yesterday. */ #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> static double const EPS = 1e-8; int a, b; double get_y(double x) { return 2 * b * sqrt((1 - x * x / a / a)); } double get_s(double l, double r) { return (get_y(l) + 4 * get_y((l + r) / 2) + get_y(r)) * (r - l) / 6; } double calc(double l, double r) { double mid = (l + r) / 2; if (fabs(get_s(l, r) - get_s(l, mid) - get_s(mid, r)) < EPS) return get_s(l, r); return calc(l, mid) + calc(mid, r); } int main() { int T; scanf("%d", &T); for (; T--;) { int l, r; scanf("%d%d%d%d", &a, &b, &l, &r); printf("%.3lf\n", calc(l, r)); } return 0; }