14658 - 하늘에서 별똥별이 빗발친다

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

14658번: 하늘에서 별똥별이 빗발친다

주의할 점

1. N*M은 500'000 * 500'000으로 전부 탐색이 불가능하다.
2. 값이 작은 K를 이용하자.
3. 별이 트램펄린 가장자리에 있을 때가 가장 많은 별을 포함하게 된다.
4. 별이 꼭짓점에 있을 때는 최대가 아닐수 있다. 다이아 몬드 모양으로 배치된 경우

코드

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;
typedef pair<int, int> pii;

int N,M,L,K;
vector<pii> stars;

void input(){
    int y, x;
    cin>>M>>N>>L>>K;

    for(int i=0;i<K;++i){
        cin>>x>>y;

        stars.push_back({y,x});
    }
}

bool chk(int sx, int ny, int ty, int tx){
    if(ty >= ny && ty <= ny + L && tx >= sx && tx <= sx + L)
        return true;

    return false;
}

void solution(){
    int ans = 987'654'321;

    for(int i=0;i<K;++i){
        int sx = stars[i].second;

        for(int j=0;j<K;++j){
            int ny = stars[j].first;
                
            int cnt = 0;
            for(int t=0;t<K;++t){
                int ty = stars[t].first;
                int tx = stars[t].second;

                if(!chk(sx, ny, ty, tx))
                    ++cnt;
            }

            ans = min(ans, cnt);
        }
    }
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}