보석 - 2492

//2492 - 보석
 
#include <iostream>
using namespace std;
 
int N, M, T, K;
int X[100];
int Y[100];
 
void init()
{
    cin >> N >> M >> T >> K;
    for(int i = 0; i<T; ++i)
        cin >> X[i] >> Y[i];
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    int ansX, ansY, ans = 0;
    int num;
    int x, y;
    for(int i = 0; i<T; ++i)
        for(int j = 0; j<T; ++j)
        {
            num = 0;
            if(X[i] + K >= N)
                x = N-K;
            else x = X[i];
 
            if(Y[j] + K >= M)
                y = M-K;
            else y = Y[j];
 
            for(int k = 0; k<T; ++k)
                if(X[k] >= x && X[k] <= x+K && Y[k] >= y && Y[k] <= y+K)
                    ++num;
            if(ans < num)
            {
                ans = num;
                ansX = x;
                ansY = y+K;
            }
        }
    
    cout << ansX << " " << ansY << "\n";
    cout << ans;
}

 

 

 

 

 

보석

정해진 정사각형 크기안에서 보석들이 가장 많이 포함되는 경우는 위쪽과 왼쪽 변에 보석이 하나씩 포함되는 경우입니다.

여러가지 예외상황들이 있는데, 하나는 고른 두점의 기울기가 음인경우(이 경우엔 더 위쪽에 있는 하나의 점이 좌상단 꼭지점이 됩니다)

다른 경우는 고른 두개의 점으로 정사각형을 만들었더니 영역 밖으로 나가는 경우입니다.

첫번째는 사실 보석의 쌍에 대해 모든 경우를 따져보면 자동으로 해결이 되는 문제입니다.

두번째는 영역밖으로 나가게되면, 해당 정사각형은 우하단에 박혀있는 정사각형에 포함되는것과 마찬가지니, 우하단에 박혀있는 정사각형으로 따져서 계산해 주면 됩니다.