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
228
题意：给出n个矩形，求周长并
思路：第一种方法和矩形面积并差不多。
先做一次对x坐标离散化，然后从下往上扫描，每扫描到一条线段，更新线段树，然后答案加上该次的整个区间被覆盖的长度与上次的差的绝对值。
再做一次对y坐标离散化，然后从左往右扫描，每扫描到一条线段，更新线段树，然后答案加上该次的整个区间被覆盖的长度与上次的差的绝对值。
C++版本一
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
const int N=20000+10;
int n,cnt=0;
int x,x2,y,y2;
int tree[N<<2];
int flag[N];
int X[N],Y[N];
struct nodex{
//int x1,x2,y1,y2;
int l,r,y,s;
nodex(){};
nodex(int l_, int r_, int y_, int s_)
{
l=l_, r=r_, y=y_, s=s_;
}
bool operator <(const nodex &S) const
{
return y<S.y;
}
}G[N];
struct nodey{
//int x1,x2,y1,y2;
int l,r,y,s;
nodey(){};
nodey(int l_, int r_, int y_, int s_)
{
l=l_, r=r_, y=y_, s=s_;
}
bool operator <(const nodey &S) const
{
return y<S.y;
}
}H[N];
int findx(int tmp, int n)
{
int l=1, r=n, mid;
while(l<=r)
{
mid=(l+r)>>1;
if(X[mid]==tmp) return mid;
else if(X[mid]<tmp) l=mid+1;
else r=mid-1;
}
}
int findy(int tmp, int n)
{
int l=1, r=n, mid;
while(l<=r)
{
mid=(l+r)>>1;
if(Y[mid]==tmp) return mid;
else if(Y[mid]<tmp) l=mid+1;
else r=mid-1;
}
}
void pushupx(int i,int l,int r){
if(flag[i]) tree[i]=X[r+1]-X[l];
else if (l==r) tree[i]=0;
else tree[i]=tree[i<<1]+tree[i<<1|1];
}
void pushupy(int i,int l,int r){
if(flag[i]) tree[i]=Y[r+1]-Y[l];
else if (l==r) tree[i]=0;
else tree[i]=tree[i<<1]+tree[i<<1|1];
}
void updata(int i,int l,int r,int L,int R,int C,int val){
if(L<=l&&r<=R){
flag[i]+=C;
if(val)
pushupx(i,l,r);
else
pushupy(i,l,r);
return;
}
int m=(l+r)/2;
if(R<=m) updata(i<<1,l,m,L,R,C,val);
else if(L>m) updata(i<<1|1,m+1,r,L,R,C,val);
else{
updata(i<<1,l,m,L,m,C,val);
updata(i<<1|1,m+1,r,m+1,R,C,val);
}
if(val)
pushupx(i,l,r);
else
pushupy(i,l,r);
}
void init(){
memset(tree,0,sizeof(tree));
memset(flag,0,sizeof(flag));
}
int main()
{
scanf("%d",&n);
memset(X,0,sizeof(X));
memset(Y,0,sizeof(Y));
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&x,&y,&x2,&y2);
G[++cnt]=nodex(x,x2,y,1);
H[cnt]=nodey(y,y2,x,1);
X[cnt]=x;
Y[cnt]=y;
G[++cnt]=nodex(x,x2,y2,-1);
H[cnt]=nodey(y,y2,x2,-1);
X[cnt]=x2;
Y[cnt]=y2;
}
int ans=0;
init();
sort(X+1,X+cnt+1);
sort(G+1,G+cnt+1);
int k=1;
for(int i=2;i<=cnt;i++)
if(X[i]!=X[i+1]) X[++k]=X[i];
int t=0;
for(int i=1;i<=cnt;i++){
int l=findx(G[i].l,k);
int r=findx(G[i].r,k)-1;
updata(1,1,k,l,r,G[i].s,1);
ans+=abs(t-tree[1]);
t=tree[1];
}
init();
sort(Y+1,Y+cnt+1);
sort(H+1,H+cnt+1);
k=1;
for(int i=2;i<=cnt;i++)
if(Y[i]!=Y[i+1]) Y[++k]=Y[i];
t=0;
for(int i=1;i<=cnt;i++){
int l=findy(H[i].l,k);
int r=findy(H[i].r,k)-1;
updata(1,1,k,l,r,H[i].s,0);
ans+=abs(t-tree[1]);
t=tree[1];
}
cout << ans << endl;
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
int n;
#define maxn 10010
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
struct Seg
{
int x1, y1, x2, y2;
}seg[maxn];
struct Line
{
int l, r, h;
int mark;
}line[maxn];
int a[maxn], b[maxn];
map <int, int> mp;
int cnt;
int ans;
bool cmp(Line l1, Line l2)
{
return l1.h < l2.h;
}
int sum[(maxn*2)<<2];
int cover[(maxn*2)<<2];
void pushup(int l, int r, int rt)
{
if(sum[rt]) cover[rt] = mp[r+1] - mp[l];
else
{
if(r == l) cover[rt] = 0;
else cover[rt] = cover[rt<<1] + cover[rt<<1|1];
}
}
void build(int l, int r, int rt)
{
cover[rt] = 0; sum[rt] = 0;
if(l == r) return;
int m = (l+r)>>1;
build(lson);
build(rson);
pushup(l, r, rt);
}
void update(int L, int R, int val, int l, int r, int rt)
{
if(L == l && R == r)
{
sum[rt] += val;
pushup(l, r, rt);
return;
}
int m = (l+r)>>1;
if(R <= m) update(L, R, val, lson);
else if(L > m) update(L, R, val, rson);
else
{
update(L, m, val, lson);
update(m+1, R, val, rson);
}
pushup(l, r, rt);
}
void slovex()
{
cnt = 0; mp.clear();
for(int i = 1; i <= n; i++)
{
a[cnt++] = seg[i].x1; a[cnt++] = seg[i].x2;
line[i*2-1].l = seg[i].x1; line[i*2-1].r = seg[i].x2;
line[i*2-1].h = seg[i].y1; line[i*2-1].mark = 1;
line[i*2].l = seg[i].x1; line[i*2].r = seg[i].x2;
line[i*2].h = seg[i].y2; line[i*2].mark = -1;
}
for(int i = 0; i < cnt; i++) b[i] = a[i];
sort(a, a+cnt);
int precnt = cnt;
cnt = unique(a, a+cnt) - a;
for(int i = 0; i < precnt; i++) mp[lower_bound(a, a+cnt, b[i]) - a + 1] = b[i];
sort(line+1, line+1+2*n, cmp);
build(1, cnt, 1);
int precover = 0;
for(int i = 1; i <= 2*n; i++)
{
int ll = lower_bound(a, a+cnt, line[i].l) - a + 1;
int rr = lower_bound(a, a+cnt, line[i].r) - a + 1;
update(ll, rr-1, line[i].mark, 1, cnt, 1);
ans += abs(precover - cover[1]);
precover = cover[1];
}
}
void slovey()
{
cnt = 0; mp.clear();
for(int i = 1; i <= n; i++)
{
a[cnt++] = seg[i].y1; a[cnt++] = seg[i].y2;
line[i*2-1].l = seg[i].y1; line[i*2-1].r = seg[i].y2;
line[i*2-1].h = seg[i].x1; line[i*2-1].mark = 1;
line[i*2].l = seg[i].y1; line[i*2].r = seg[i].y2;
line[i*2].h = seg[i].x2; line[i*2].mark = -1;
}
for(int i = 0; i < cnt; i++) b[i] = a[i];
sort(a, a+cnt);
int precnt = cnt;
cnt = unique(a, a+cnt) - a;
for(int i = 0; i < precnt; i++) mp[lower_bound(a, a+cnt, b[i]) - a + 1] = b[i];
sort(line+1, line+1+2*n, cmp);
build(1, cnt, 1);
int precover = 0;
for(int i = 1; i <= 2*n; i++)
{
int ll = lower_bound(a, a+cnt, line[i].l) - a + 1;
int rr = lower_bound(a, a+cnt, line[i].r) - a + 1;
update(ll, rr-1, line[i].mark, 1, cnt, 1);
ans += abs(precover - cover[1]);
precover = cover[1];
}
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int cast = 0;
while(~scanf("%d", &n))
{
cnt = 0; mp.clear();
for(int i = 1; i <= n; i++) scanf("%d%d%d%d", &seg[i].x1, &seg[i].y1, &seg[i].x2, &seg[i].y2);
ans = 0;
slovex(); slovey();
printf("%d\n", ans);
}
return 0;
} C++版本三
扫描线求周长
其实这就和之前的东西一样了，只是需要横竖扫两遍。
值得注意的是，因为一条入边必然对应着一条出边，因而不需要lazy只需要维护一个覆盖数即可
其次 入边要排在出边得前面，才能保证前面的优化正确
下面是代码，我写的比较麻烦，是求周长的，稍微改一下就变成了求面积的，本类题其实常伴随着离散化等操作
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 40000+5
#define M 80000+5
using namespace std;
int ans,n;
struct data
{
int l,r,c,m;
int lazy;
data () {}
}tr[M];
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct ROW
{
int y1,y2;
int x;
int in;
bool operator < (const ROW &z)const
{
return x^z.x?x<z.x:in<z.in;
}
void output(int i)
{
printf("ROW[%d] x=%d %d %d\n",i,x-40,y1-40,y2 -40);
}
}r[N];
struct LINE
{
int y;
int x1,x2;
int in;
bool operator < (const LINE &z)const
{
return y^z.y?y<z.y:in<z.in;
}
void output(int i)
{
printf("ROW[%d] y=%d %d %d\n",i,y-40,x1-40,x2-40 );
}
}l[N];
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r;
if(l==r)
{ tr[k].lazy=tr[k].m=tr[k].c=0;return;}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tr[k].lazy=tr[k].m=tr[k].c=0;
}
int CCC = 0;
void updata(int k)
{
if(tr[k].l==tr[k].r)
{
if(tr[k].c)
tr[k].m=1;
else
tr[k].m=0;
return ;
}
if(tr[k].c)
tr[k].m=tr[k].r-tr[k].l+1;
else
tr[k].m=tr[k<<1].m+tr[k<<1|1].m;
//if(!tr[k].c)
// tr[k].c=min(tr[k<<1].c,tr[k<<1|1].c);
return ;
}
void down(int k)
{
int tmp=tr[k].lazy;
tr[k<<1].lazy+=tmp;
tr[k<<1].c+=tmp;
updata(k<<1);
tr[k<<1|1].lazy+=tmp;
tr[k<<1|1].c+=tmp;
updata(k<<1|1);
tr[k].lazy=0;
return;
}
void change(int k,int l,int r,int x)
{
if(l==tr[k].l && r==tr[k].r)
{
//tr[k].lazy+=x;
tr[k].c+=x;
updata(k);
if(CCC <= 3)
{
printf("k=%d lazy=%d c=%d m=%d tl=%d tr=%d l=%d r=%d\n", k, tr[k].lazy, tr[k].c,
tr[k].m, tr[k].l-40, tr[k].r-40, l-40, r-40);
}
return ;
}
//if(tr[k].lazy)
// down(k);
int mid=(tr[k].l+tr[k].r)>>1;
if(r<=mid)
change(k<<1,l,r,x);
else if(l>mid)
change(k<<1|1,l,r,x);
else
{
change(k<<1,l,mid,x);
change(k<<1|1,mid+1,r,x);
}
updata(k);
if(CCC <= 3)
{
printf("2 k=%d lazy=%d c=%d m=%d tl=%d tr=%d l=%d r=%d\n", k, tr[k].lazy, tr[k].c,
tr[k].m, tr[k].l-40, tr[k].r-40, l-40, r-40);
}
}
/*int ask(int k,int l,int r)
{
if(l==tr[k].l && r==tr[k].r)
return tr[k].m;
if(tr[k].lazy)
down(k);
int mid=(tr[k].r+tr[k].l)>>1;
if(r<=mid)
return ask(k<<1,l,r);
else if(l>mid)
return ask(k<<1|1,l,r);
return ask(k<<1,l,mid)+ask(k<<1,mid+1,r);
}*/
void add(int x1,int y1,int x2,int y2)
{
static int cnt=0;
r[++cnt].x=x1,r[cnt].y1=y1,r[cnt].y2=y2;
r[cnt].in=0;
l[cnt].y=y1,l[cnt].x1=x1,l[cnt].x2=x2;
l[cnt].in=0;
r[++cnt].x=x2,r[cnt].y1=y1,r[cnt].y2=y2;
r[cnt].in=1;
l[cnt].y=y2,l[cnt].x1=x1,l[cnt].x2=x2;
l[cnt].in=1;
return ;
}
void out()
{
for(int i=1;i<=200;++i)
{
printf("%d %d %d %d\n",tr[i].l,tr[i].r,tr[i].c,tr[i].m);
}
return ;
}
int main()
{
//freopen("seg.in", "r", stdin);
//freopen("tt.out", "w", stdout);
cin>>n;
for(int i=1,x1,x2,y1,y2;i<=n;++i)
{
x1=read()+10001,y1=read()+10001,x2=read()+10001,y2=read()+10001;
add(x1,y1,x2,y2);
}
sort(l+1,l+2*n+1);
sort(r+1,r+2*n+1);
build(1,1,20002);
int tmp=0;
for(int i=1;i<=2*n;++i)
{
CCC=4;
if(!l[i].in)
change(1,l[i].x1,l[i].x2-1,1);
else
change(1,l[i].x1,l[i].x2-1,-1);
int ss=tr[1].m;
//printf("pre=%d now=%d +=%d\n", tmp, ss, abs(ss-tmp) );
ans+=abs(ss-tmp);
tmp=ss;
//out();
}
//printf("%d\n",ans );
build(1,1,20002);
tmp=0;
for(int i=1;i<=2*n;++i)
{
if(!r[i].in)
change(1,r[i].y1,r[i].y2-1,1);
else
change(1,r[i].y1,r[i].y2-1,-1);
int ss=tr[1].m;
//printf("pre=%d now=%d +=%d\n", tmp, ss, abs(ss-tmp) );
ans+=abs(ss-tmp);
tmp=ss;
}
cout<<ans;
}
京公网安备 11010502036488号