正題

題目鏈接：https://vijos.org/p/1056

---

大意

給出幾個(gè)矩形的左上坐標(biāo)和右下坐標(biāo)求所有矩形覆蓋了的總面積。

---

解題思路

就是一個(gè)簡(jiǎn)單的離散而已。

---

代碼

#include<iostream> #include<algorithm> using namespace std; long long xx[201],yy[201],lrx[101],lry[101],rux[101],ruy[101],x[201],y[201],res; int n,mm,m1,m2; bool flag; long long abss(long long x) {if (x<0) return -x;return x; } int main() {ios::sync_with_stdio(0);//優(yōu)化cin,coutcin>>n;for (int i=1;i<=n;i++){cin>>lrx[i]>>lry[i]>>rux[i]>>ruy[i];xx[++mm]=lrx[i];yy[mm]=lry[i];xx[++mm]=rux[i];yy[mm]=ruy[i];}stable_sort(xx+1,xx+1+mm);stable_sort(yy+1,yy+1+mm);//排序x[1]=xx[1];y[1]=yy[1];m1=1;m2=1;for (int i=2;i<=mm;i++)if (xx[i]!=xx[i-1])x[++m1]=xx[i];//去重for (int i=2;i<=mm;i++)if (yy[i]!=yy[i-1])y[++m2]=yy[i];//去重for (int i=1;i<m1;i++){for (int j=1;j<m2;j++){flag=false;for (int k=1;k<=n;k++)if (x[i]>=lrx[k]&&x[i+1]<=rux[k]&&y[j]>=lry[k]&&y[j+1]<=ruy[k])//判斷是否在改矩形里{flag=true;break;}if (flag){res+=abss((x[i]-x[i+1])*(y[j]-y[j+1]));//計(jì)算大小}}}cout<<res; }

總結(jié)

以上是生活随笔為你收集整理的vijos1056-图形面积【离散化】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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