BZOJ2731 [HNOI2012]三角形覆盖问题

2015.02.26 16:38 Thu| 23 visits oi_2015| 2015_刷题日常| Text

Solution

从前,在一次引起众怒的考试中,16bitwar同学找了这道题:

eolv 小朋友没有开 long long 扣掉了一半分,在 BZOJ 上却过掉了 QoQ。

做法很简单残暴:

注意到每一个三角形都是等腰直角三角形且一直角边平行于 x 轴,可以从下向上扫描,用循环链表维护经过当前扫描线的三角形,代码实现及其简单。

理论时间复杂度 $\mathcal O(N^2)$,实际表现由于三角形位置随机且题意决定不会卡这个做法,因此实际上比理论复杂度好得多。当然,也有 $\mathcal O(N\log N)$ 做法,不过长度被完虐 2333。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 10005
#define H 2000000

int n, ans, cnt, l[N], r[N], w[H + 5];

struct data
{
    int x, y, d;
    inline bool operator < (const data &t) const { return y < t.y; }
} tri[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
        tri[i].x = read(), tri[i].y = read(), tri[i].d = read();
    sort(tri + 1, tri + n + 1);
    int now = 0;
    for (int i = 0; i <= H; ++i)
    {
        ans += now;
        for (int j = r[0]; j; j = r[j])
        {
            --tri[j].d;
            if (tri[j].d <= 0) r[l[j]] = r[j], l[r[j]] = l[j];
            if (--w[tri[j].x + tri[j].d] == 0) --now;
        }
        ans += now;
        while (tri[cnt + 1].y == i)
        {
            ++cnt;
            if (tri[cnt].d <= 0) continue;
            for (int j = r[0]; j; j = r[j])
                if (tri[j].x <= tri[cnt].x &&
                    tri[cnt].x + tri[cnt].d <= tri[j].x + tri[j].d)
                    goto fail;
            l[cnt] = l[0]; r[l[0]] = cnt; l[0] = cnt;
            for (int j = tri[cnt].x; j < tri[cnt].x + tri[cnt].d; ++j)
                if ((w[j]++) == 0) ++now;
            fail: continue;
        }
    }
    cout << fixed << setprecision(1) << double(ans) / 2 << endl;
}