금강석 - 2496

//2496 - 금강석
 
#include <iostream>
#include <queue>
using namespace std;
 
int N, M, T, K;
int X[100], Y[100];
 
int convertX(int x, int y)
{
    return x - y;
}
 
int convertY(int x, int y)
{
    return x + y;
}
 
void init()
{
    cin >> N >> M >> T >> K;
    int x, y;
    for (int i = 0; i < T; ++i)
    {
        cin >> x >> y;
        X[i] = convertX(x, y);
        Y[i] = convertY(x, y);
    }
}
 
int main()
{
    init();
    int x, y;
    int num, ans = 0, ansX, ansY;
    queue<int> xQ, yQ;
    for (int i = 0; i < T; ++i)
        for (int j = 0; j < T; ++j)
        {
            x = X[i];
            y = Y[j];
            if ((x + y) % 2)
            {
                xQ.push(x), xQ.push(x), xQ.push(x - 1), xQ.push(x + 1);
                yQ.push(y + 1), yQ.push(y - 1), yQ.push(y), yQ.push(y);
            }
            else
                xQ.push(x), yQ.push(y);
 
            while (!xQ.empty())
            {
                num = 0;
                x = xQ.front(), xQ.pop();
                y = yQ.front(), yQ.pop();
                int u = y-x;
                if (x + y + K > 2 * N)
                    x = N - u/2 - K/2, y = N + u/2 - K/2;
 
                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 + K / 2;
                    ansY = y + K / 2;
                }
            }
        }
    cout << (ansX + ansY) / 2 << " " << (ansY - ansX) / 2 << "\n";
    cout << ans;
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/2496

2496번: 금강석

 

 

 

 

 

 

금강석

https://onedaycoding.tistory.com/127문제의 응용버전입니다.

이 문제의 좌표계를 (0, 0)을 기준으로 반시계 방향으로 45도 회전시켜주고, 금강석이 밑변과 왼쪽 변에 포함되는 사각형안을 탐색하도록 했습니다.

이때 주의해야할 점이 탐색하는 사각형의 꼭지점이 원래 좌표계에서 정수가 아닌 경우가 나올수도 있습니다. 이 경우엔 그 근처 4개의 점들을 모두 탐색하도록 하였습니다.