题解 P1222 【三角形】

本题的一种非正解：$Simpson$积分 用时: 280ms / 内存: 2359KB 在时间上劣于正解，但是对于这题绰绰有余 显然，根据$Simpson$积分公式，  直接用的话误差会超大，于是用自适应$Simpson$就行了，记得调好$eps$的值，太精确了会$TLE$，太大了会$WA$ 温馨提示：不是正解，所以需要$O2$ 代码: ``` #include <iostream> #include <cstdio> #include <limits.h> #include <cstdlib> #include <algorithm> #include <iostream> #include <queue> #include <vector> #include <cmath> #include <ctime> using namespace std; const int maxn = 5500; class Tri{ public: int x, y, r; Tri(int x = 0, int y = 0, int z = 0): x(x), y(y), r(z){} }T[maxn]; const double eps = 1e-9; inline int read(){ char ch = getchar(); int u = 0, f = 1; while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar();} while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar();} return u * f; } int a[maxn], n; vector<pair<double, double> >seg; bool equal(double a, double b){ return fabs(a - b) <= eps; } double f(double X){ seg.clear(); for (int i = 1; i <= n; ++i){ if (T[i].x < X && T[i].x + T[i].r > X){ double tmp = T[i].r - (X - T[i].x); seg.push_back(make_pair(T[i].y, T[i].y + tmp)); } } if (!seg.size()) return 0.0; sort(seg.begin(), seg.end()); double len = 0, last = seg[0].first; for (int i = 0; i < seg.size(); ++i) if (seg[i].second - last > 0) { len += seg[i].second - max(seg[i].first, last); last = seg[i].second; } return len; } int x_pos[maxn]; double calc(double l, double r, double lv, double rv){ double mid = (l + r) / 2.0; return (lv + 4.0 * f(mid) + rv) * (r - l) / 6.0; } double simpson(double l, double r, double now, double lv, double rv){ double mid = (l + r) / 2.0, mv = f(mid); double L = calc(l, mid, lv, mv); double R = calc(mid, r, mv, rv); if (equal(L + R, now)) return now; return simpson(l, mid, L, lv, mv) + simpson(mid, r, R, mv, rv); } int main() { //freopen("data.txt","r",stdin); scanf("%d", &n); int ct = 0; for (int i = 1; i <= n; ++i){ int a = read(), b = read(), c = read(); T[i] = Tri(a, b, c); x_pos[++x_pos[0]] = a; x_pos[++x_pos[0]] = a + c; } sort(x_pos + 1, x_pos + 1 + x_pos[0]); for (int i = 1; i <= x_pos[0]; ++i) if (i == 1 || x_pos[i] != x_pos[i - 1]) x_pos[++ct] = x_pos[i]; //printf("ct = %d\n", ct); //for (int i = 1; i <= ct; ++i) printf("%d ", x_pos[i]); double ans = 0; for (int i = 2; i <= ct; ++i){ double l = x_pos[i - 1] + 2 * eps, r = x_pos[i] - 2 * eps, Left = f(l), Right = f(r); ans += simpson(l, r, calc(l, r, Left, Right), Left, Right); //printf("%lf ", ans); } printf("%.1lf", ans); return 0; } ```