BZOJ1502 [NOI2005]月下柠檬树

今天几乎讲了一天的算几。或者说能听的只有算几。然后就去做了一道基础题。

刚开始的时候比较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);
}