poj 1177 Picture (线段树 扫描线 离散化 矩形周长并)

题目链接

题意:给出n个矩形,每个矩形给左下 和 右上的坐标,求围成的周长的长度。

分析:

首先感谢大神的博客,最近做题经常看大神的博客:http://www.cnblogs.com/kuangbin/

沿x轴离散化。和之前的矩阵面积并有点像。

但是一定要去重,否则会错

 #include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL __int64
#define lson l, mid, 2*rt
#define rson mid+1, r, 2*rt+1
const int maxn = +;
using namespace std;
int n, x[maxn];
struct node
{
int l, r, cnt;
int lf, rf;
int num, c; //num是分支的个数,即当前的x段有多少段,可以想象一段是对应两个竖边的。
bool lc, rc; //表示左端是否覆盖,和右端是否覆盖,用来判断x段是否练成一块了
}tr[maxn*];
struct Line
{
int y, x1, x2, f;
}line[maxn];
bool cmp(Line a, Line b)
{
return a.y < b.y;
}
void build(int l, int r, int rt)
{
tr[rt].l = l; tr[rt].r = r;
tr[rt].lf = x[l]; tr[rt].rf = x[r];
tr[rt].cnt = ; tr[rt].num = ;
tr[rt].c = ;
tr[rt].lc = tr[rt].rc = false;
if(tr[rt].l+ == tr[rt].r) return;
int mid = (l+r)/;
build(l, mid, *rt);
build(mid, r, *rt+);
}
void calen(int rt)
{
if(tr[rt].c>)
{
tr[rt].cnt = tr[rt].rf-tr[rt].lf;
tr[rt].num = ;
tr[rt].lc = tr[rt].rc = true; //这整个一块都覆盖了,左右端点自然也覆盖
return;
}
if(tr[rt].l+ == tr[rt].r)
{
tr[rt].cnt = tr[rt].num = ;
tr[rt].lc = tr[rt].rc = false;
}
else
{
tr[rt].cnt = tr[*rt].cnt+tr[*rt+].cnt;
tr[rt].lc = tr[*rt].lc; tr[rt].rc = tr[*rt+].rc;//自己这块没有覆盖,看一下子节点是否有覆盖
tr[rt].num = tr[*rt].num+tr[*rt+].num;
if(tr[*rt].rc && tr[*rt+].lc) tr[rt].num --; //如果当前这个节点的子节点左的右
//覆盖和右的左覆盖说明中间已经练成一片了,所以分支-1
}
}
void update(int rt, Line e)
{
if(tr[rt].lf==e.x1 && tr[rt].rf==e.x2)
{
tr[rt].c += e.f;
calen(rt);
return;
}
if(e.x2<=tr[*rt].rf) update(*rt, e);
else if(e.x1>=tr[*rt+].lf) update(*rt+, e);
else
{
Line tmp;
tmp = e;
tmp.x2 = tr[*rt].rf;
update(*rt, tmp);
tmp = e;
tmp.x1 = tr[*rt+].lf;
update(*rt+, tmp);
}
calen(rt);
}
int main()
{
int i, t, ans, pre;
int x1, x2, y1, y2;
while(~scanf("%d", &n))
{
t = ; ans = ; pre = ;
for(i = ; i < n; i++)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
line[t].x1 = x1; line[t].x2 = x2;
line[t].y = y1; line[t].f = ;
x[t++] = x1;
line[t].x1 = x1; line[t].x2 = x2;
line[t].y = y2; line[t].f = -;
x[t++] = x2;
}
sort(x, x+t);
sort(line, line+t, cmp);
int y = unique(x, x+t)-x; //去重
build(, y-, ); for(i = ; i < t-; i++)
{
update(, line[i]);
ans += tr[].num**(line[i+].y-line[i].y); //竖线的长度
ans += abs(tr[].cnt-pre); //加上 新增的横线 或者 是减少的横线
pre = tr[].cnt;
}
update(, line[i]);
ans += abs(tr[].cnt-pre);
printf("%d\n", ans);
}
return ;
}
上一篇:配置git DiffMerge工具


下一篇:416. Partition Equal Subset Sum