今天几乎讲了一天的算几。或者说能听的只有算几。然后就去做了一道基础题。
刚开始的时候比较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);
}
