<div class="post_brief"><p>
今天几乎讲了一天的算几。或者说能听的只有算几。然后就去做了一道基础题。</p>
刚开始的时候比较naive,把相交的情况想简单了,打算直接上数学,然后悲剧地发现还有其它的不好算交点的情况,于是就去写simpson了。
simpson就是一个估计用的,s = (4 * f(mid) + f(l) + f(r))*(r-l)/6。至于为啥是对的就不知道了。反正比较能用。然后每次直接去扫一遍所有能交的地方,取max就行了,比挨个算交点方便许多。
然后第一次写,代码也比较乱。
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm>using namespace std;
const int maxn = 509; const double pi = asin(1) * 2; const double eps = 1e-6;
#define x1 x1 #define x2 x2 #define y1 y1 #define y2 y2
int n; double tht, x[maxn], h[maxn], r[maxn]; double crd[maxn]; double x1[maxn], x2[maxn], y1[maxn], y2[maxn]; bool c[maxn];
inline int sgn(double x) { if (fabs(x) < eps) return 0; else return (x < 0) ? -1 : 1; }
inline double sqr(double x) { return x * x; }
void calc() { for (int i = 0; i < n; ++ i) { int u(i), v(i + 1); if (sgn(x[u] - r[u] - x[v] + r[v]) <= 0 && sgn(x[u] + r[u] - x[v] - r[v]) >= 0) { c[i] = 0; } else { double ctht((r[u] - r[v]) / (x[v] - x[u])), stht(sqrt(1 - sqr(ctht))); x1[i] = x[u] + r[u] * ctht; y1[i] = r[u] * stht; x2[i] = x[v] + r[v] * ctht; y2[i] = r[v] * stht; c[i] = 1; } } }
double f(double x0) { double y(0); for (int i = 0; i <= n; ++ i) if (x0 >= x[i] - r[i] && x0 <= x[i] + r[i]) y = max(y, sqrt(sqr(r[i]) - sqr(x0 - x[i]))); for (int i = 0; i < n; ++ i) if (c[i] && sgn(x0 - x1[i]) >= 0 && sgn(x0 - x2[i]) <= 0) y = max(y, (y1[i] * (x2[i] - x0) + y2[i] * (x0 - x1[i])) / (x2[i] - x1[i])); return y; }
inline double integ(double l, double r) { return (f(l) + f(r) + f((l + r) / 2) * 4) * (r - l) / 6; }
double simpson(double l0, double r0) { double mid((l0 + r0) / 2.0); double a(integ(l0, r0)); double b(integ(l0, mid)); double c(integ(mid, r0)); if (fabs(a - b - c) < eps) return b + c; else return simpson(l0, mid) + simpson(mid, r0); }
int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif
double l0, r0; scanf("%d%lf", &n, &tht); for (int i = 0; i <= n; ++ i) scanf("%lf", h + i); for (int i = 0; i <= n; ++ i) { if (i) h[i] += h[i - 1]; x[i] = h[i] / tan(tht); } l0 = r0 = x[n]; for (int i = 0; i < n; ++ i) { scanf("%lf", r + i); l0 = min(l0, x[i] - r[i]); r0 = max(r0, x[i] + r[i]); } r[n] = 0; calc(); printf("%.2lf\n", simpson(l0, r0) * 2.0);
}