hdu 1828 Picture(线段树&扫描线&周长并)Picture

65 阅读 0 评论 43 点赞

我是靠谱客的博主乐观缘分，最近开发中收集的这篇文章主要介绍hdu 1828 Picture(线段树&扫描线&周长并)Picture ，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Picture

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2578 Accepted Submission(s): 1363

Problem Description

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.

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

Source

IOI 1998

Recommend

linle | We have carefully selected several similar problems for you: 1255 1823 3333 1543 3458

题意：

给你一些平行于坐标轴的矩形。问你这些矩形组成的连通块的轮廓线的周长。

思路：

有两种方法，不过常用的第二种，两种都说一下。
第一种：
把矩形分成横线和竖线去处理，可知是完全相同的操作，我们来讲下怎么算出横线部分，竖线部分就是照搬即可。
将横线保存在一个表中，按横线所处的竖直位置排序（升序），另外每条横线带一个标记值，原矩形的下线为1，上线为-1（对应过去就是插入线段和删除线段）
从低到高扫描横线,没扫到一条横线就能计算出一部分横线值。计算方法是算出现在总区间的被覆盖的长度，然后求出与上一次的总区间的覆盖长度的差（即相减求绝对值），因为每次添加了一条线段，如果没有没有使总区间覆盖长度发生变化，说明这条线段其实在多边形的内部，被覆盖掉了，不能计算，只要能引起总区间长度发生变化的，说明该线段不被覆盖不被包含，要计算
而竖线部分的做法是一样的，把竖线保存在一个表中，按水平位置排序（升序），每条横线带一个标记值，原矩形的左线为1，右线为-1，然后同样地操作

第二种：
上面的方法显得有点“笨”，相同的工作做了两次，可不可以只扫描一次矩形就求出答案，是可以的，但是我们要改进一下线段树节点记录的信息
每个线段树的节点要记录几个信息
1.l,r，该节点代表的线段的左右端点坐标
2.cl,cr，是一个标记量，只有0,1，表示这个节点左右两个端点没有被覆盖，有为1，无为0
3.cnt，表示这个区间被重复覆盖了几次
4.len，这个区间被覆盖的长度
5.num，这个区间被多少条线段覆盖
好像区间[0,10]，被[1,2],[4,5]覆盖，那么num=2
好像区间[0,10],被[1,3][4,5]覆盖，那么num=1，因为他们刚好连在一起了
好像区间[0,10],被[1,5][2,6]覆盖，那么num=1，因为还是连起来的一段
前面的工作是相同的，把横线保存在一个表中，按竖直位置排序，然后从下往上扫描所有横线，在这个方法中，每次扫描一条横线，都能计算出两不部分值，一部分是横线的，一部分是竖线的
而计算横线部分的方法和第一种方法是一样的，即求出【现在这次总区间被覆盖的长度和上一次总区间被覆盖的长度的差的绝对值】，另外怎么算竖线部分呢?首先我们要知道添加了这条横线后会有多少条竖线，答案是2*num，所以为什么要记录num呢，因为总区间被num条线段覆盖，那么必定有2*num的端点，这些端点其实就是连着竖线，那么这些竖线的长度是多少呢？
就是【下一条横线的高度-现在这条横线的高度】，只要把这个高度乘上2*num即可

以上转自here.

既然思路清楚了。代码就很顺利的出来了。

详细见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=10010;
#define lson L,mid,ls
#define rson mid+1,R,rs
int n,m;
int cov[maxn<<2],num[maxn<<2],len[maxn<<2],H[maxn];//不用初始化。默认为0且每次最后一条线段都会清0的。
bool cl[maxn<<2],cr[maxn<<2];
struct node
{
int x1,x2,h,v;
node(int a=0,int b=0,int c=0,int d=0):x1(a),x2(b),h(c),v(d){}
} seg[maxn];
int abss(int x){
return x<0?-x:x;
}
bool cmp(node a,node b)
{
return a.h<b.h;
}
void init()
{
sort(H,H+m);
m=unique(H,H+m)-H;
}
int Hash(int x)
{
return lower_bound(H,H+m,x)-H;
}
void PushUp(int L,int R,int rt)
{
if(cov[rt])//有标记肯定整块覆盖了
len[rt]=H[R+1]-H[L],cl[rt]=cr[rt]=true,num[rt]=1;
else if(L==R)//没有左右儿子了。
len[rt]=0,cl[rt]=cr[rt]=false,num[rt]=0;
else//没有整块覆盖但是被部分覆盖了
{
len[rt]=len[rt<<1]+len[rt<<1|1];
cl[rt]=cl[rt<<1],cr[rt]=cr[rt<<1|1];
num[rt]=num[rt<<1]+num[rt<<1|1];
if(cr[rt<<1]&&cl[rt<<1|1])
num[rt]-=1;
}
}
void update(int L,int R,int rt,int l,int r,int d)
{
if(l<=L&&R<=r)
{
cov[rt]+=d;
PushUp(L,R,rt);
return;
}
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
if(l<=mid)
update(lson,l,r,d);
if(r>mid)
update(rson,l,r,d);
PushUp(L,R,rt);
}
int main()
{
int i,ptr,x1,x2,y1,y2,ans,pre;
while(~scanf("%d",&n))
{
for(i=ptr=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
H[ptr]=x1;
seg[ptr++]=node(x1,x2,y1,1);
H[ptr]=x2;
seg[ptr++]=node(x1,x2,y2,-1);
}
m=ptr,ans=pre=0;
init();
sort(seg,seg+ptr,cmp);
for(i=0,ptr--;i<ptr;i++)
{
update(0,m-1,1,Hash(seg[i].x1),Hash(seg[i].x2)-1,seg[i].v);//m个结点m-1条线段
ans+=2*(seg[i+1].h-seg[i].h)*num[1]+abss(len[1]-pre);
pre=len[1];
}
update(0,m-1,1,Hash(seg[i].x1),Hash(seg[i].x2)-1,seg[i].v);
ans+=abss(len[1]-pre);
printf("%dn",ans);
}
return 0;
}