poj 1177 || HDU 1828 Picture （线段树扫描线求图形并的周长）

59 阅读 0 评论 39 点赞

我是靠谱客的博主眯眯眼夕阳，最近开发中收集的这篇文章主要介绍poj 1177 || HDU 1828 Picture （线段树扫描线求图形并的周长），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

题意：求图形并后的周长

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)
#define eps 1e-8
typedef __int64 ll;
#define fre(i,a,b)
for(i = a; i <b; i++)
#define free(i,b,a) for(i = b; i >= a;i--)
#define mem(t, v)
memset ((t) , v, sizeof(t))
#define ssf(n)
scanf("%s", n)
#define sf(n)
scanf("%d", &n)
#define sff(a,b)
scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf
printf
#define bug
pf("Hin")
using namespace std;
#define INF 0x3f3f3f3f
#define N 10000
struct stud{
int le,ri;
int num;
//当前节点覆盖（y的差值）的次数
int lcover,rcover;
//左端点是否覆盖，右....
int cover;
//当前区间是否被覆盖
int len;
//当前区间被覆盖的x轴并的长度
}f[N*4];
struct studd{
int x1,x2;
int h,type;
bool operator < (const studd b) const
{
return h<b.h;
}
}e[N*2];
int x[N*2];
map<int ,int>mp;
void pushup(int pos)
{
if(f[pos].cover)
//如果当前被覆盖
{
f[pos].lcover=f[pos].rcover=f[pos].num=1;//那么这一个区间的y只有一个，因为求得是并图形的周长
f[pos].len=x[f[pos].ri]-x[f[pos].le];
//例如 3 4 被覆盖，而 2 8 被覆盖，那么y周长只能算一次
return ;
//因为3 4 是被2 8覆盖的
}
if(f[pos].le+1==f[pos].ri)
//叶子节点&&没有被覆盖
{
f[pos].lcover=f[pos].rcover=0;
f[pos].len=f[pos].num=0;
return ;
}
f[pos].lcover=f[L(pos)].lcover;
//当前节点没有被覆盖
f[pos].rcover=f[R(pos)].rcover;
f[pos].num=f[L(pos)].num+f[R(pos)].num-(f[L(pos)].rcover&f[R(pos)].lcover);
//左边的段数+右边的段数
如果这一个区间是连在一起的，应该减去 1
f[pos].len=f[L(pos)].len+f[R(pos)].len; //当前的x距离
}
void build(int pos,int le,int ri)
{
f[pos].le=le;
f[pos].ri=ri;
f[pos].len=0;
f[pos].cover=0;
f[pos].lcover=f[pos].rcover=f[pos].num=0;
if(le+1==ri) return ;
int mid=MID(le,ri);
build(L(pos),le,mid);
build(R(pos),mid,ri);
}
void update(int pos,int le,int ri,int type)
{
if(f[pos].le==le&&f[pos].ri==ri)
{
f[pos].cover+=type;
pushup(pos);
return ;
}
int mid=MID(f[pos].le,f[pos].ri);
if(mid>=ri)
update(L(pos),le,ri,type);
else
if(mid<le)
update(R(pos),le,ri,type);
else
{
if(mid>le)
update(L(pos),le,mid,type);
if(mid<ri)
update(R(pos),mid,ri,type);
}
pushup(pos);
}
int main()
{
int i,j,k,n;
int x1,x2,y1,y2;
while(~sf(n))
{
k=0;
fre(i,0,n)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x[k]=x1;
e[k].x1=x1;
e[k].x2=x2;
e[k].type=1;
e[k++].h=y1;
x[k]=x2;
e[k].x1=x1;
e[k].x2=x2;
e[k].type=-1;
e[k++].h=y2;
}
sort(e,e+k);
sort(x,x+k);
n=unique(x,x+k)-x;
mp.clear();
fre(i,0,n)
mp[x[i]]=i;
n--;
build(1,0,n);
int ans=0,temp=0;
fre(i,0,k)
{
int le=mp[e[i].x1];
int ri=mp[e[i].x2];
update(1,le,ri,e[i].type);
ans+=f[1].num*2*(e[i+1].h-e[i].h);
ans+=abs(f[1].len-temp);
temp=f[1].len;
}
pf("%dn",ans);
}
return 0;
}