学步园

HDU_1828

    以前只用离散化的思想写过这个题，现在又结合上线段树重新写了一遍。如果希望只沿一个方向扫描一遍就求出周长的话，那么相当于需要用两种方式分别求水平和竖直部分的周长。比如我们沿x方向扫描，那么竖直方向上的边长就需要通过矩形覆盖扫描线的总长度的变化值来计算，而水平方向上的边长就需要用点数乘以区间跨度去计算。

    其实感觉也可以在两个方法中任选一个，分别沿x、y方向各扫描一遍，也可以求出最后的周长。

    此外，如果我们沿x方向扫描，并按矩形覆盖的扫描线的总长度的变化值去计算竖直部分的边长的话，那么最初在对线段排序时，同一x值的线段一定要是矩形右边的边在前，是矩形左边的边在后。也就是说同一x位置上，要先进行添加边的操作，再进行删除边的操作，这是因为如果两条竖直边重合或有公共部分的话，我们如果先删再添就会多计算一部分长度。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 10010
int N, M, ty[4 * MAXD], num[4 * MAXD], lc[4 * MAXD], rc[4 * MAXD], len[4 * MAXD], cnt[4 * MAXD];
struct Seg
{
int x, y1, y2, col;
}seg[4 * MAXD];
int cmps(const void *_p, const void *_q)
{
    Seg *p = (Seg *)_p, *q = (Seg *)_q;
if(p->x == q->x)
return p->col > q->col ? -1 : 1;
return p->x < q->x ? -1 : 1;
}
int cmpy(const void *_p, const void *_q)
{
int *p = (int *)_p, *q = (int *)_q;
return *p < *q ? -1 : 1;
}
void build(int cur, int x, int y)
{
int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;
    len[cur] = lc[cur] = rc[cur] = num[cur] = cnt[cur] = 0;
if(x == y)
return ;
    build(ls, x, mid);
    build(rs, mid + 1, y);
}
void update(int cur, int x, int y)
{
int ls = cur << 1, rs = (cur << 1) | 1;
if(cnt[cur])
    {
        len[cur] = ty[y + 1] - ty[x];
        lc[cur] = rc[cur] = 1;
        num[cur] = 2;
    }
else if(x == y)
        len[cur] = lc[cur] = rc[cur] = num[cur] = 0;
else
    {
        len[cur] = len[ls] + len[rs];
        lc[cur] = lc[ls], rc[cur] = rc[rs];
        num[cur] = num[ls] + num[rs];
if(rc[ls] && lc[rs])
            num[cur] -= 2;
    }
}
void init()
{
int i, j, k, x1, y1, x2, y2;
for(i = 0; i < N; i ++)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        j = i << 1, k = (i << 1) | 1;
        seg[j].x = x1, seg[k].x = x2;
        seg[j].y1 = seg[k].y1 = y1, seg[j].y2 = seg[k].y2 = y2;
        seg[j].col = 1, seg[k].col = -1;
        ty[j] = y1, ty[k] = y2;
    }
    N <<= 1;
    qsort(seg, N, sizeof(seg[0]), cmps);
    qsort(ty, N, sizeof(ty[0]), cmpy);
    M = -1;
for(i = 0; i < N; i ++)
if(i == 0 || ty[i] != ty[i - 1])
            ty[++ M] = ty[i];
    build(1, 0, M - 1);
}
void refresh(int cur, int x, int y, int s, int t, int c)
{
int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;
if(x >= s && y <= t)
    {
        cnt[cur] += c;
        update(cur, x, y);
return ;
    }
if(mid >= s)
        refresh(ls, x, mid, s, t, c);
if(mid + 1 <= t)
        refresh(rs, mid + 1, y, s, t, c);
    update(cur, x, y);
}
int BS(int y)
{
int mid, min = 0, max = M + 1;
for(;;)
    {
        mid = (min + max) >> 1;
if(mid == min)
break;
if(ty[mid] <= y)
            min = mid;
else
            max = mid;
    }
return mid;
}
void solve()
{
int i, j, k, ans, prelen;
    ans = prelen = 0;
    seg[N].x = seg[N - 1].x;
for(i = 0; i < N; i ++)
    {
        j = BS(seg[i].y1), k = BS(seg[i].y2);
        refresh(1, 0, M - 1, j, k - 1, seg[i].col);
        ans += num[1] * (seg[i + 1].x - seg[i].x);
        ans += abs(len[1] - prelen);
        prelen = len[1];
    }
    printf("%d\n", ans);
}
int main()
{
while(scanf("%d", &N) == 1)
    {
        init();
        solve();
    }
return 0;
}