題目鏈接：點(diǎn)擊查看

題目大意：給出n個(gè)矩形的左下角坐標(biāo)和右上角坐標(biāo)，求出其總面積，注意，矩形會(huì)重疊，重疊部分只計(jì)算一次

題目分析：如果暴力做需要考慮容斥原理，兩兩矩形組合判斷是否重合，十分麻煩而且時(shí)間復(fù)雜度也十分的高，這里用到了線段樹和掃描線的思想，我通過這篇博客學(xué)習(xí)的，感覺寫的不錯(cuò)：點(diǎn)擊查看

然后我用自己的風(fēng)格寫了一下這個(gè)題，具體需要注意的我都寫在注釋里了，直接上代碼吧：

對(duì)了，需要注意的是，對(duì)于掃描線這種題目，如果數(shù)據(jù)不為整數(shù)或數(shù)據(jù)量過大，我們需要對(duì)線段樹的區(qū)間進(jìn)行離散化處理

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=210;struct Node {int l,r,cover;double right,left;double len; }tree[N<<2];vector<double>v;struct node {double x,upy,downy;int into;node(){x=upy=downy=0;into=0;} }line[N];bool cmp(node a,node b) {return a.x<b.x; }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].cover=0;tree[k].len=0;tree[k].left=v[l-1];tree[k].right=v[r-1];if(l+1==r)return;int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid,r);//注意這里是mid到r，舉個(gè)例子，如果端點(diǎn)有四個(gè)，分別是10,20,30,40,我們希望的區(qū)間是[10,20],[20,30],[30,40]而不是[10,20]和[30,40] }void pushup(int k) {if(tree[k].cover>0)//如果被覆蓋了，長(zhǎng)度更新為兩個(gè)端點(diǎn)之差 tree[k].len=tree[k].right-tree[k].left;else if(tree[k].l+1==tree[k].r)//如果沒被覆蓋，并且是“葉節(jié)點(diǎn)”，長(zhǎng)度更新為0 tree[k].len=0;else//如果沒被覆蓋，但不是葉子節(jié)點(diǎn)，長(zhǎng)度更新為左兒子和右兒子之和 tree[k].len=tree[k<<1].len+tree[k<<1|1].len; }void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].cover+=val;pushup(k);return;}update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }int main() { // freopen("input.txt","r",stdin);int n;int kase=0;while(scanf("%d",&n)!=EOF&&n){v.clear();for(int i=1;i<=n;i++){double x1,y1,x2,y2;scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);v.push_back(y1);v.push_back(y2);line[i].downy=line[i+n].downy=y1;line[i].upy=line[i+n].upy=y2;line[i].x=x1;line[i+n].x=x2;line[i].into=1;line[i+n].into=-1;}sort(v.begin(),v.end());//離散化--排序 sort(line+1,line+1+2*n,cmp);//對(duì)x坐標(biāo)排序 v.erase(unique(v.begin(),v.end()),v.end());//離散化--去重 int len=v.size();//得到離散化后的y坐標(biāo)的長(zhǎng)度 double ans=0;build(1,1,len);//建樹需要建len個(gè)點(diǎn)，相鄰的每?jī)蓚€(gè)點(diǎn)所組成了len-1個(gè)區(qū)間 for(int i=1;i<=2*n;i++)//遍歷2*n個(gè)x點(diǎn) {ans+=tree[1].len*(line[i].x-line[i-1].x);//每次結(jié)果相加 int l=lower_bound(v.begin(),v.end(),line[i].downy)-v.begin()+1;//求出離散化后下面的y的編號(hào) int r=lower_bound(v.begin(),v.end(),line[i].upy)-v.begin()+1;//求出離散化后上面的y的編號(hào) update(1,l,r,line[i].into);//更新區(qū)間覆蓋情況 }printf("Test case #%d\nTotal explored area: %.2f\n\n",++kase,ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 1542 Atlantis(线段树+扫描线)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。