WUPC2012 F : 最後の問題
問題概要
2次元グリッドの格子点上に点がいくつかある。4点選んで軸に平行な長方形をつくり、内部に点がないようにしたい。面積の最大値を求める問題。
解法
長方形の2点の選び方を全探索する。内部に点があるかどうかは累積和を計算しておけばO(1)で判定できる。
acceptされたコード
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 10000; const int MAX_W = 1000; int accum[MAX_W+1][MAX_W+1]; int on[MAX_W][MAX_W]; int N; pair<int,int> ps[MAX_N]; vector<int> ys[MAX_W]; void init(){ scanf("%d", &N); for(int i=0; i<N; ++i){ int x, y; scanf("%d%d", &x, &y); ++on[x][y]; ps[i] = make_pair(x, y); ys[x].push_back(y); } } int solve(){ sort(ps, ps+N); for(int i=0; i<MAX_W; ++i){ for(int j=0; j<MAX_W; ++j){ accum[i+1][j+1] = accum[i+1][j] + accum[i][j+1] - accum[i][j] + on[i][j]; } } int ans = 0; for(int x=0; x<MAX_W; ++x)if(ys[x].size() >= 2){ sort(ys[x].begin(), ys[x].end()); for(int xx=x+1; xx<MAX_W; ++xx)if(ys[xx].size() >= 2){ for(int i=0; i<(int)ys[x].size(); ++i){ for(int j=i+1; j<(int)ys[x].size(); ++j){ const int y = ys[x][i], yy = ys[x][j]; if( !(on[xx][y] && on[xx][yy]) ){ continue; } if(xx <= x + 1 || yy <= y + 1 || accum[xx][yy] + accum[x+1][y+1] - (accum[xx][y+1] + accum[x+1][yy]) == 0){ ans = max(ans, (yy-y)*(xx-x)); } } } } } return ans; } int main(){ init(); printf("%d\n", solve()); return 0; }