Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "The Maximum Numbers of Overlaps"
https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B
平面上にN枚に長方形のシールが貼られています。各シールの辺は、x軸またはy軸に
平行で、i個目のシールの左上の座標は (x1[i],y1[i])、右下の座標は(x2[i],y2[i])です。
重なっているシールの枚数が最も多い部分の、重なっているシールの枚数を求めてください。
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #DSL_5_B : The Maximum Numbers of Overlaps
/* Aizu Online Judge in C++ #DSL_5_B : The Maximum Numbers of Overlaps https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int n; int s[1111][1111]; int main(void){ cin>>n; for(int i=0;i<n;i++){ int x,y,x2,y2; cin>>x>>y>>x2>>y2; s[x][y]++; s[x][y2]--; s[x2][y]--; s[x2][y2]++; } for(int i=0;i<=1000;i++){ for(int j=1;j<=1000;j++){ s[i][j]+=s[i][j-1]; } } for(int j=0;j<=1000;j++){ for(int i=1;i<=1000;i++){ s[i][j]+=s[i-1][j]; } } int ans=0; for(int i=0;i<=1000;i++){ for(int j=0;j<=1000;j++){ ans=max(ans,s[i][j]); } } cout<<ans<<endl; return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/