原題鏈接：https://www.luogu.com.cn/problem/P1856
矩形周長Picture
題目背景
墻上貼著許多形狀相同的海報、照片，它們的邊都是水平和垂直的，每個矩形圖片可能部分或全部的覆寫了其他圖片，所有矩形合并后的邊長稱為周長，
題目描述
撰寫一個程式計算周長，
如圖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
題解
跟矩形的面積并類似，也是利用掃描線思想用資料結構維護一維，再按照另一維延伸、進行操作，不過周長的變化不如面積直觀，但是經過觀察還是可以得出規律的：
- 對于水平的邊，添加/刪去一條邊以后新增的邊長是更新前后總的水平線段長度之差的絕對值，
- 對于豎直的邊，添加/刪去一條邊以后新增的邊長是水平線段的數量 × 2 × \times 2\times ×2×豎直方向移動的距離，
大🔥稍微手玩幾個例子就可以理解了，因為圖不太好畫我就不配圖解了，結合代碼還是很好理解的[doge]，
要注意的是，如果有兩條有重合的邊，要把下邊排在前面、上邊排在后面，否則這兩條邊重合的本來應該被合并消去的部分就會被計算到總邊長里去，
因為計算豎直邊需要用到線段條數，所以我們還需要維護連續的線段條數 c o t cot cot以及這個區間是否左/右連續 l c o n / r c o n lcon/rcon lcon/rcon，在合并左右子樹的資訊時，如果左子樹右連續且右子樹左連續，則該節點的線段條數就是左右子樹線段條數之和減一，
代碼
#include<bits/stdc++.h>
#define ls v<<1
#define rs v<<1|1
using namespace std;
const int M=1e6+5;
struct Edge{
int le,ri,h,val;
}edge[M<<1];
bool cmp(Edge a,Edge b){return a.h==b.h?a.val>b.val:a.h<b.h;}
struct node{
int le,ri,len,cov,cot;
bool lcon,rcon;
}tree[M<<2];
int n,tot,x[M],cot,ans;
void up(int v)
{
if(tree[v].cov)tree[v].len=tree[v].ri-tree[v].le,tree[v].lcon=tree[v].rcon=tree[v].cot=1;
else tree[v].len=tree[ls].len+tree[rs].len,tree[v].lcon=tree[ls].lcon,tree[v].rcon=tree[rs].rcon,tree[v].cot=tree[ls].cot+tree[rs].cot-(tree[ls].rcon&tree[rs].lcon);
}
void build(int v,int le,int ri)
{
tree[v].le=x[le],tree[v].ri=x[ri+1];
if(le==ri)return;
int mid=le+ri>>1;
build(ls,le,mid),build(rs,mid+1,ri);
}
void cover(int v,int le,int ri,int val)
{
if(le<=tree[v].le&&tree[v].ri<=ri)
{
tree[v].cov+=val;
up(v);
return;
}
if(le<tree[ls].ri)cover(ls,le,ri,val);
if(tree[rs].le<ri)cover(rs,le,ri,val);
up(v);
}
void in()
{
scanf("%d",&n);
for(int i=1,a,b,c,d;i<=n;++i)
scanf("%d%d%d%d",&a,&b,&c,&d),edge[++cot]=(Edge){a,c,b,1},edge[++cot]=(Edge){a,c,d,-1},x[++tot]=a,x[++tot]=c;
}
void ac()
{
sort(x+1,x+1+tot);
tot=unique(x+1,x+1+tot)-x-1;
build(1,1,tot-1);
sort(edge+1,edge+1+cot,cmp);
for(int i=1,pre=0;i<cot;++i)
{
cover(1,edge[i].le,edge[i].ri,edge[i].val);
ans+=abs(tree[1].len-pre),pre=tree[1].len;
ans+=tree[1].cot*(edge[i+1].h-edge[i].h)<<1;
}
printf("%d\n",ans+edge[cot].ri-edge[cot].le);
}
int main()
{
in(),ac();
system("pause");
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255970.html
標籤：其他