题解 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;
}