题目背景
墙上贴着许多形状相同的海报、照片。它们的边都是水平和垂直的。每个矩形图片可能部分或全部的覆盖了其他图片。所有矩形合并后的边长称为周长。
题目描述
编写一个程序计算周长。
如图1所示7个矩形。
如图2所示，所有矩形的边界。所有矩形顶点的坐标都是整数。
输入输出格式
输入格式：
输入文件的第一行是一个整数N（0<=N<5000），表示有多少个矩形。接下来N行给出了每一个矩形左下角坐标和右上角坐标（所有坐标的数值范围都在-10000到10000之间）。
输出格式：
输出文件只有一个正整数，表示所有矩形的周长。
输入输出样例
输入样例#1： 复制
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
输出样例#1： 复制
228
扫描线线段树
其实能够找到的一些题解的线段树都暴力的很，如果稍微数据强一点就能卡，但是这题数据实在是太弱了QAQ
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 5005
#define MAXM 10005
#define X first
#define Y second
#define pii pair<int,int>
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if('-'==ch)f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct Node{
int L,R,p,b;
Node(int p1=,int p2=,int p3=,int p4=){
L=p1,R=p2,p=p3,b=p4;
}
};
bool comp(const Node &p1,const Node &p2){
if(p1.p!=p2.p){
return (p1.p<p2.p);
}
else{
return (p1.b>p2.b);
}
}
int n;
vector<Node> vx,vy;
void init(){
n=read();
for(int i=;i<=n;i++){
int x1=read(),y1=read(),x2=read(),y2=read();
x1+=,y1+=,x2+=,y2+=;
vx.push_back(Node(x1,x2,y1,));vx.push_back(Node(x1,x2,y2,-));
vy.push_back(Node(y1,y2,x1,));vy.push_back(Node(y1,y2,x2,-));
}
sort(vx.begin(),vx.end(),comp);sort(vy.begin(),vy.end(),comp);
n=*;
}
int dat[MAXM<<],tag[MAXM<<];
void pushdown(int k){
int lc=(k<<),rc=(k<<|);
dat[lc]+=tag[k],dat[rc]+=tag[k];
tag[lc]+=tag[k],tag[rc]+=tag[k];
tag[k]=;
}
void pushup(int k){
dat[k]=min(dat[k<<],dat[k<<|]);
}
void add(int a,int b,int k,int L,int R,int x){
if(b<=L||R<=a){
return;
}
else if(a<=L&&R<=b){
dat[k]+=x;
tag[k]+=x;
}
else{
if(tag[k]){
pushdown(k);
}
add(a,b,k<<,L,(L+R)>>,x);
add(a,b,k<<|,(L+R)>>,R,x);
pushup(k);
}
}
int query(int a,int b,int k,int L,int R){
if(b<=L||R<=a){
return ;
}
if(L+==R){
return (dat[k]?:);
}
else if(a<=L&&R<=b&&dat[k]){
return R-L;
}
else{
if(tag[k]){
pushdown(k);
}
int lc=query(a,b,k<<,L,(L+R)>>);
int rc=query(a,b,k<<|,(L+R)>>,R);
return (lc+rc);
}
}
int Abs(int x){
return (x>?x:-x);
}
void solve(){
int ans=;
for(int i=;i<vx.size();i++){
int x=vx[i].L,y=vx[i].R,b=vx[i].b;
int cnt1=query(x,y,,,n+);
add(x,y,,,n+,b);
int cnt2=query(x,y,,,n+);
ans+=Abs(cnt1-cnt2);
// printf("%d ",Abs(cnt1-cnt2));
}
// printf("\n");
for(int i=;i<vy.size();i++){
int x=vy[i].L,y=vy[i].R,b=vy[i].b;
int cnt1=query(x,y,,,n+);
add(x,y,,,n+,b);
int cnt2=query(x,y,,,n+);
ans+=Abs(cnt1-cnt2);
// printf("%d ",Abs(cnt1-cnt2));
}
printf("%d\n",ans);
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
init();
solve();
return ;
}