hdu 4052(扫描线)

题意：有一个大矩形宽×高是w×h，然后有n个在大矩形内部的小矩形左下角坐标和右上角坐标给出，这些小矩形作为阻碍，让1×m的长条无法放入大矩形，问1×m的长条有多少种放法。
题解：首先能想到比起直接计算，简洁计算也就是用总的方法数-小矩形占的方法数会更容易求。然后思路就转化为计算每个小矩形占了多少种放法数。每个小矩形(x1,y1-(m-1)),(x2,y2)内的每一个点都无法作为长条的起点，所以把这些点都刨除在外就行了，那么就可以这样计算这些小矩形的面积并，然后用总放法数减掉就是解。横向和纵向分开考虑会更容易计算。注意要把所有矩形右和上边界扩大一保证结果正确。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#define ll long long
using namespace std;
const int N = 100005;
struct Line {
    int lx, rx, h;
    int flag;
    Line(int a, int b, int c, int d): lx(a), rx(b), h(c), flag(d) {}
    bool operator < (const Line& a) const { return h < a.h; }
};
struct Rec {
    int x1, y1, x2, y2;
}rec[N];
ll tree[N << 2], res;
int flag[N << 2], n;
vector<int> a;
vector<Line> line;
map<int, int> mp;

void pushup(int k, int left, int right) {
    if (flag[k])
        tree[k] = a[right] - a[left];
    else if (left + 1 == right)
        tree[k] = 0;
    else
        tree[k] = tree[k * 2] + tree[k * 2 + 1];
}

void modify(int k, int left, int right, int l, int r, int v) {
    if (l <= left && right <= r) {
        flag[k] += v;
        pushup(k, left, right);
        return;
    }
    int mid = (left + right) / 2;
    if (l < mid)
        modify(k * 2, left, mid, l, r, v);
    if (r > mid)
        modify(k * 2 + 1, mid, right, l, r, v);
    pushup(k, left, right);
}

void solve(int flag1, int w, int h, int m) {
    a.clear(), line.clear(), mp.clear();
    memset(tree, 0, sizeof(tree));
    memset(flag, 0, sizeof(flag));
    a.push_back(1);
    a.push_back(w + 1);
    int temp = max(1, h - m + 2);
    line.push_back(Line(1, w + 1, temp, 1));
    line.push_back(Line(1, w + 1, h + 1, -1));
    for (int i = 1; i <= n; i++) {
        if (!flag1) {
            scanf("%d%d%d%d", &rec[i].x1, &rec[i].y1, &rec[i].x2, &rec[i].y2);
            rec[i].x2++, rec[i].y2++;
        }
        else {
            swap(rec[i].x1, rec[i].y1);
            swap(rec[i].x2, rec[i].y2);
        }
        int temp = max(1, rec[i].y1 - m + 1);
        line.push_back(Line(rec[i].x1, rec[i].x2, temp, 1));
        line.push_back(Line(rec[i].x1, rec[i].x2, rec[i].y2, -1));
        a.push_back(rec[i].x1);
        a.push_back(rec[i].x2);
    }
    sort(line.begin(), line.end());
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    int sz = a.size(), sz2 = line.size();
    for (int i = 0; i < sz; i++)
        mp[a[i]] = i;
    for (int i = 0; i < sz2; i++) {
        if (i != 0)
            res -= tree[1] * (ll)(line[i].h - line[i - 1].h);
        modify(1, 0, sz, mp[line[i].lx], mp[line[i].rx], line[i].flag);
    }
}

int main() {
    int w, h, m;
    while (scanf("%d%d%d%d", &w, &h, &n, &m) == 4) {
        res = (ll)w * h * 2;
        solve(0, w, h, m);
        solve(1, h, w, m);
        if (m == 1) printf("%lldn", res / 2);
        else printf("%lldn", res);
    }
    return 0;
}

最后

以上就是顺利红牛为你收集整理的hdu 4052(扫描线)的全部内容，希望文章能够帮你解决hdu 4052(扫描线)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。