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;
}