BZOJ1502 [NOI2005]月下柠檬树

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

刚开始的时候比较naive，把相交的情况想简单了，打算直接上数学，然后悲剧地发现还有其它的不好算交点的情况，于是就去写simpson了。

simpson就是一个估计用的，s = (4 * f(mid) + f(l) + f(r))*(r-l)/6。至于为啥是对的就不知道了。反正比较能用。然后每次直接去扫一遍所有能交的地方，取max就行了，比挨个算交点方便许多。

然后第一次写，代码也比较乱。

1	#include <cstdio>
2	#include <cstring>
3	#include <cmath>
4	#include <algorithm>
5	
6	using namespace std;
7	
8	const int maxn = 509;
9	const double pi = asin(1) * 2;
10	const double eps = 1e-6;
11	
12	#define x1 _x1_
13	#define x2 _x2_
14	#define y1 _y1_
15	#define y2 _y2_
16	
17	int n;
18	double tht, x[maxn], h[maxn], r[maxn];
19	double crd[maxn];
20	double x1[maxn], x2[maxn], y1[maxn], y2[maxn];
21	bool c[maxn];
22	
23	inline int sgn(double x) {
24		if (fabs(x) < eps)
25			return 0;
26		else
27			return (x < 0) ? -1 : 1;
28	}
29	
30	inline double sqr(double x) {
31		return x * x;
32	}
33	
34	void calc() {
35		for (int i = 0; i < n; ++ i) {
36			int u(i), v(i + 1);
37			if (sgn(x[u] - r[u] - x[v] + r[v]) <= 0 && sgn(x[u] + r[u] - x[v] - r[v]) >= 0) {
38				c[i] = 0;
39			}
40			else {
41				double ctht((r[u] - r[v]) / (x[v] - x[u])), stht(sqrt(1 - sqr(ctht)));
42				x1[i] = x[u] + r[u] * ctht; 
43				y1[i] = r[u] * stht;
44				x2[i] = x[v] + r[v] * ctht;
45				y2[i] = r[v] * stht;
46				c[i] = 1;
47			}
48		}
49	}
50	
51	double f(double x0) {
52		double y(0);
53		for (int i = 0; i <= n; ++ i)
54			if (x0 >= x[i] - r[i] && x0 <= x[i] + r[i])
55				y = max(y, sqrt(sqr(r[i]) -  sqr(x0 - x[i])));
56		for (int i = 0; i < n; ++ i)
57			if (c[i] && sgn(x0 - x1[i]) >= 0 && sgn(x0 - x2[i]) <= 0)
58				y = max(y, (y1[i] * (x2[i] - x0) + y2[i] * (x0 - x1[i])) / (x2[i] - x1[i]));
59		return y;
60	}
61	
62	inline double integ(double l, double r) {
63		return (f(l) + f(r) + f((l + r) / 2) * 4) * (r - l) / 6;
64	}
65	
66	double simpson(double l0, double r0) {
67		double mid((l0 + r0) / 2.0);
68		double a(integ(l0, r0));
69		double b(integ(l0, mid));
70		double c(integ(mid, r0));
71		if (fabs(a - b - c) < eps)
72			return b + c;
73		else
74			return simpson(l0, mid) + simpson(mid, r0);
75	}
76	
77	int main() {
78	#ifndef ONLINE_JUDGE
79		freopen("in.txt", "r", stdin);
80	#endif
81	
82		double l0, r0;
83		scanf("%d%lf", &n, &tht);
84		for (int i = 0; i <= n; ++ i)
85			scanf("%lf", h + i);
86		for (int i = 0; i <= n; ++ i) {
87			if (i)
88				h[i] += h[i - 1];
89			x[i] = h[i] / tan(tht);
90		}
91		l0 = r0 = x[n];
92		for (int i = 0; i < n; ++ i) {
93			scanf("%lf", r + i);
94			l0 = min(l0, x[i] - r[i]);
95			r0 = max(r0, x[i] + r[i]);
96		}
97		r[n] = 0;
98		calc();
99		printf("%.2lf\n", simpson(l0, r0) * 2.0);
100	}
101