题解 P3219 【[HNOI2012]三角形覆盖问题】

· · 题解

题意

（很好理解吧qaq）
给一堆等腰三角形，求面积并

前言

这题最快有O(n\log(n))的做法，用到平衡树，可查阅这位dalao题解
其他dalao们的做法都是O(n^2)加玄学优化的
由于数据水，我这个蒟蒻只会以下这种水法。。。

题解

从下往上扫描线（可一格一格地扫），当前要计算的面积就是一堆梯形，它会由斜边产生缺口（即上底比下底短）。可以把它们合起来算，记录 下底长之和 和 缺口大小（上下底的差） 即可更新答案。

扫到一个新的三角形，枚举其斜边整点，更新数据。（具体更新方法请见代码）

时间复杂度O(\sum d)=O(n\times d)
我也不知道怎么过的，反正就是过了。。。
最慢（#10）143ms

代码

#include<bits/stdc++.h>
#define db double
#define ll long long
#define inf 1000009
#define eps 1e-11
#define INF 1e11
#define rd(n) {n=0;char ch;int f=0;do{ch=getchar();if(ch=='-'){f=1;}}while(ch<'0'||ch>'9');while('0'<=ch&&ch<='9'){n=(n<<1)+(n<<3)+ch-48;ch=getchar();}if(f)n=-n;}
using namespace std;

int n;
int x[inf],d[inf];
int s[inf],mx[inf];
/*s[i]表示第i行梯形上底与下地之差*/
/*mx[i]表示当前第i列的最高点y值*/
vector <int> pos[inf];

int main(){
    rd(n)
    int y,maxy=0;
    for (int i=1;i<=n;i++){
        rd(x[i]) rd(y) rd(d[i])
        pos[y].push_back(i);
        maxy=max(maxy,y+d[i]);
    }
    ll ans=0;
    int now=0;//now是当前行下底长
    for (int i=0;i<=maxy;i++){
        ans+=(ll)(now*2-s[i]);
        now-=s[i];
        int cnt=pos[i].size();
        for (int j=0;j<cnt;j++){
            int id=pos[i][j];
            for (int k=0;k<d[id];k++){
                if (i+d[id]-k>mx[x[id]+k]){
                    if (mx[x[id]+k]<=i){
                        now++;
                    }
/*若当前列旧的最高点小于当前，而现在在此列增加了更高的三角形，下一行的梯形的下底会加大一格*/
                    s[mx[x[id]+k]]--;
/*旧的缺口被填上，在更高点产生新的缺口*/                    
                    mx[x[id]+k]=i+d[id]-k;
                    s[mx[x[id]+k]]++;
                }
            }
        }
    }
    printf("%.1lf\n",(db)ans/2.0);
    return 0;
}