1-2. 오렌지 나무 ★★★★☆

#include <iostream>
#include <vector>

using namespace std;

vector<int> x;
vector<int> y;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int w, h, t, s, a, b;
	cin >> w >> h >> t >> s;
	
	for(int i = 0; i < t; i++)
	{
		cin >> a >> b;
		x.push_back(a);
		y.push_back(b);
	}
	
	int x1 = 0, y1 = 0;
	int count = 0;
	int res = 0;
	
	for(int i = 0; i < t; i++)
	{
		for(int j = 0; j < t; j++)
		{
			count = 0;
			for(int k = 0; k < t; k++)
			{
				if(x[k] >= x[i] && x[k] <= x[i] + s && y[k] >= y[j] && y[k] <= y[j] + s)
					count++;
			}
			if(res < count) res = count;
		}
	}

	cout << res << "\n";
	
	return 0;
}

1. 이전에 영역 선택 large 문제 풀이처럼 다이나믹 프로그래밍으로 풀어봤는데, 영역문제는 좌표가 아닌 영역 문제라서 위 문제처럼 좌표 문제를 풀기 힘들었다.

2. 한 지점으로부터 x좌표 +3, y좌표 +3 까지 확인해가면서 전체 영역을 확인하는 방법으로 시도했는데 Time Limit이 났다.

만약 h와 w가 각각 100,000, 나무의 개수가 100그루라면 최악의 경우 100,000 * 100,000 * 100 의 경우의 수를 확인해야한다.

3. 필요없는 영역은 확인하지 않도록 영역 자르기를 해야했다. 2번 방법은 나무가 없는 s * s 영역도 확인해서 시간이 오래걸렸다. 영역을 자르는 방법은 먼저 각 나무의 x좌표만 뽑는다. 그 x좌표와 전체 나무의 y좌표로 (x1, yx) 좌표를 만들어서 그 지점에서부터 s * s 크기만큼 확인한다.