Picture【扫描线+线段树】

A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter.

Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.

Picture【扫描线+线段树】

The corresponding boundary is the whole set of line segments drawn in Figure 2.

Picture【扫描线+线段树】

The vertices of all rectangles have integer coordinates.

Input

Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.

0 <= number of rectangles < 5000
All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area.

Please process to the end of file.

Output

Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.

Sample Input

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

Sample Output

一开始想用两次暴力去写的，就是竖着一遍再横着一遍去查询的……后来想到了一个好的主意~~（为了偷懒）~~，然后就决定开始尝试一下，就决定开始写了，就是，对于每个查询的X轴上的长度，可以通过作与上一个状态的差值的绝对值来得到的，那么要乘以多少次Y轴的长度，就只会受到连续区间段的影响……推出来的，然后写了一下，就过了。

就是，我们更新每次区间的时候，不忘更新点是否是断点，断点得记录下断出来的区间数，要是不是断点，就要记录下此区间内的断区间数目，然后推下去就是了，返回到tree[1]，就可以得到该树的左右连续区间数目。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e4 + 5;
int N, num, cnt_x, X[maxN], lazy[maxN<<2];
struct node
{
    int lx, rx, y, val;
    node(int a=0, int b=0, int c=0, int d=0):lx(a), rx(b), y(c), val(d) {}
}line[maxN];
bool cmp(node e1, node e2) { return e1.y < e2.y; }
struct TREE
{
    int val, range; //val是此时该段被覆盖次数
    bool lc, rc;
    TREE(int a=0, bool b=false, bool c=false, int d=0, int f=0):val(a), lc(b), rc(c), range(d) {}
}tree[maxN<<2];
inline void buildTree(int rt, int l, int r)
{
    lazy[rt] = 0;
    tree[rt] = TREE();
    if(l == r) return;
    int mid = HalF;
    buildTree(Lson);
    buildTree(Rson);
}
void pushup(int rt, int l, int r)
{
    if(lazy[rt])
    {
        tree[rt].val = X[r + 1] - X[l];
        tree[rt].range = 1;
        tree[rt].lc = tree[rt].rc = true;
    }
    else if(l == r) tree[rt] = TREE();
    else
    {
        tree[rt].val = tree[lsn].val + tree[rsn].val;
        tree[rt].range = tree[lsn].range + tree[rsn].range;
        tree[rt].lc = tree[lsn].lc;
        tree[rt].rc = tree[rsn].rc;
        if(tree[lsn].rc && tree[rsn].lc) tree[rt].range--;
    }
}
void update(int rt, int l, int r, int ql, int qr, int val)
{
    if(ql <= l && qr >= r)
    {
        lazy[rt] += val;
        pushup(myself);
        return;
    }
    int mid = HalF;
    if(qr <= mid) update(QL, val);
    else if(ql > mid) update(QR, val);
    else { update(QL, val); update(QR, val); }
    pushup(myself);
}
inline void init()
{
    num = 0;
    cnt_x = 1;
}
int main()
{
    while(scanf("%d", &N)!=EOF)
    {
        init();
        for(int i=1; i<=N; i++)
        {
            int lx, ly, rx, ry;
            scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
            line[++num] = node(lx, rx, ly, 1);
            X[num] = lx;
            line[++num] = node(lx, rx, ry, -1);
            X[num] = rx;
        }
        sort(X + 1, X + num + 1);
        sort(line + 1, line + num + 1, cmp);
        for(int i=2; i<=num; i++) if(X[i] != X[i-1]) X[++cnt_x] = X[i];
        buildTree(1, 1, cnt_x);
        ll ans = 0, las = 0;
        for(int i=1; i<num; i++)
        {
            int l = (int)(lower_bound(X + 1, X + cnt_x + 1, line[i].lx) - X);
            int r = (int)(lower_bound(X + 1, X + cnt_x + 1, line[i].rx) - X - 1);
            update(1, 1, cnt_x, l, r, line[i].val);
            ans += abs(tree[1].val - las) + tree[1].range * 2 * (line[i+1].y - line[i].y);
            las = tree[1].val;
        }
        ans += line[num].rx - line[num].lx;
        printf("%lld\n", ans);
    }
    return 0;
}

Picture【扫描线+线段树】

相关推荐