POJ 1177 Picture(Segment Tree Scanning Lines)

Description

矩形相交，求合并后的周长

Analyze

算面积的时候主乘法，算周长的时候主加法

平行于扫描线方向上新增的长度 = abs(新len[1] - 旧len[1])

垂直于扫描线方向上新增的长度 = tot[1] * (e[i + 1].h - e[i].h)

新增三个变量，ls(区间左端点是否被覆盖)、rs、tot(扫描线切割了几段)

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;

int n;
int num;
int X[N];
int cnt[N << 2 | 1];
int len[N << 2 | 1];
int tot[N << 2 | 1];
bool ls[N << 2 | 1];
bool rs[N << 2 | 1];

struct edge
{
    int l, r, h;
    int flag;
    edge(int a, int b, int c, int d):l(a), r(b), h(c), flag(d){}
    edge(){}
    bool operator < (const edge & t)const
    {
        return h < t.h;
    }
}e[N];

void up(int o, int L, int R)
{
    if(cnt[o])
    {
        tot[o] = 2;
        ls[o] = rs[o] = 1;
        len[o] = X[R + 1] - X[L];
    }
    else if(L == R)
        tot[o] = len[o] = 0, ls[o] = rs[o] = 0;
    else
    {
        len[o] = len[o << 1] + len[o << 1 | 1];
        ls[o] = ls[o << 1], rs[o] = rs[o << 1 | 1];
        tot[o] = tot[o << 1] + tot[o << 1 | 1];
        if(rs[o << 1] && ls[o << 1 | 1])
            tot[o] -= 2;
    }
}

void update(int o, int L, int R, int l, int r, int val)
{
    if(L > r || R < l)
        return ;
    if(l <= L && R <= r)
    {
        cnt[o] += val;
        up(o, L, R);
        return ;
    }
    if(L == R)
        return ;

    int mid = (L + R) >> 1;
    update(o << 1, L, mid, l, r, val);
    update(o << 1 | 1, mid + 1, R, l, r, val);
    up(o, L, R);
}

int main()
{
    int t = 1;
    while(~scanf("%d", &n) && n)
    {
        num = 0;
        memset(len, 0, sizeof(len));
        memset(cnt, 0, sizeof(cnt));
        memset(tot, 0, sizeof(tot));
        memset(ls, 0, sizeof(ls));
        memset(rs, 0, sizeof(rs));
        int a, b, c, d;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d %d %d %d", &a, &b, &c, &d);
            X[num] = a;
            e[num++] = edge(a, c, b, 1);
            X[num] = c;
            e[num++] = edge(a, c, d, -1);
        }

        sort(e, e + num);
        sort(X, X + num);
        int m = unique(X, X + num) - X;

        long long ans = 0;
        int last = 0;
        for(int i = 0; i < num; ++i)
        {
            int l = lower_bound(X, X + m, e[i].l) - X;///Segment Tree begins with 0
            int r = lower_bound(X, X + m, e[i].r) - X - 1;
            update(1, 0, m - 1, l, r, e[i].flag);
            ans += tot[1] * (e[i + 1].h - e[i].h);
            ans += abs(len[1] - last);
            last = len[1];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

扫描线题目主要是针对特殊变量（像本题目中tot、ls、rs）设计up函数