HDU 1828 扫描线求周长

95 阅读 0 评论 63 点赞

我是靠谱客的博主高高裙子，最近开发中收集的这篇文章主要介绍HDU 1828 扫描线求周长，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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.

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

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.

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

可以用两颗线段树维护两个维度，但这样较慢，这里采用一颗线段树维护y轴并计算x轴对应关系。

特别注意周长是区间长度不是点的个数，用线段树维护时要先将点转化为区间。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cmath>
#include <vector>
using namespace std;
const int NUM=20010;
const int COD=10000;
struct point
{
int l,r,f;
int lc,rc,ic,dv;
//lc,rc表示区间左右端点是否被覆盖，ic表示区间内不相交线段数。
//dv表示区间被覆盖次数,当dv==-1时表示区间不均匀
}tree[NUM*4];
int LL,RR,val,interval;
struct edge
{
int x,y1,y2,val;
}scanline[10005];
bool cmp(edge a,edge b)
{
if(a.x==b.x)
return a.val>b.val; //当x相同时要先计算入边，不然这一对边会被多计算
return a.x<b.x;
}
void build(int k,int LL,int RR)
{
tree[k].l=LL,tree[k].r=RR;
tree[k].lc=tree[k].rc=tree[k].ic=tree[k].f=tree[k].dv=0;
if(tree[k].l==tree[k].r)
return;
int bet=(tree[k].l+tree[k].r)>>1;
build(k<<1,LL,bet);
build(k<<1|1,bet+1,RR);
}
void pushdown(int k)
{
tree[k<<1].f+=tree[k].f;
tree[k<<1|1].f+=tree[k].f;
tree[k<<1].dv+=tree[k].f;
tree[k<<1|1].dv+=tree[k].f;
if(tree[k<<1].dv!=0) tree[k<<1].lc=tree[k<<1].rc=tree[k<<1].ic=1;
else tree[k<<1].lc=tree[k<<1].rc=tree[k<<1].ic=0;
if(tree[k<<1|1].dv!=0) tree[k<<1|1].lc=tree[k<<1|1].rc=tree[k<<1|1].ic=1;
else tree[k<<1|1].lc=tree[k<<1|1].rc=tree[k<<1|1].ic=0;
tree[k].f=0;
}
void pushup(int k)
{
tree[k].lc=tree[k<<1].lc;
tree[k].rc=tree[k<<1|1].rc;
if(tree[k<<1].dv==tree[k<<1|1].dv) tree[k].dv=tree[k<<1].dv;
else tree[k].dv=-1;
tree[k].ic=tree[k<<1].ic+tree[k<<1|1].ic;
if(tree[k<<1].rc==1&&tree[k<<1|1].lc==1)
tree[k].ic--;
}
void change(int k)
{
if(LL<=tree[k].l&&RR>=tree[k].r&&tree[k].dv!=-1){
tree[k].f+=val;
tree[k].dv+=val;
if(tree[k].dv!=0) tree[k].lc=tree[k].rc=tree[k].ic=1;
else tree[k].lc=tree[k].rc=tree[k].ic=0;
return;
}
if(tree[k].f) pushdown(k);
int bet=(tree[k].l+tree[k].r)/2;
if(LL<=bet) change(k<<1);
if(RR>bet) change(k<<1|1);
pushup(k);
}
void ask(int k)
{
if(LL<=tree[k].l&&RR>=tree[k].r&&tree[k].dv!=-1){
if(tree[k].dv>0)
interval+=tree[k].r-tree[k].l+1;
return;
}
if(tree[k].f) pushdown(k);
int bet=(tree[k].l+tree[k].r)>>1;
if(LL<=bet) ask(k<<1);
if(RR>bet) ask(k<<1|1);
}
int main()
{
int n;
while(scanf("%d",&n)!=-1){
build(1,0,20005);
int index=0;
for(int i=0;i<n;i++){
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
scanline[index].val=1;
scanline[index].x=x1+COD;
scanline[index].y1=y1+COD;
scanline[index++].y2=y2+COD-1; //注意-1
scanline[index].val=-1;
scanline[index].x=x2+COD;
scanline[index].y1=y1+COD;
scanline[index++].y2=y2+COD-1; //注意-1
}
int ans=0,befiv=0;
sort(scanline,scanline+index,cmp);
for(int i=0;i<index-1;i++){
LL=scanline[i].y1,RR=scanline[i].y2;
val=scanline[i].val;
change(1);
interval=0;
LL=0,RR=20005;
ask(1);
ans+=abs(interval-befiv)+tree[1].ic*2*(scanline[i+1].x-scanline[i].x);
befiv=interval;
}
ans+=befiv;
printf("%dn",ans);
}
return 0;
}