백준 8983, 사냥꾼

개요

문제 링크
골드 4, Bisect
M개의 점으로부터 맨하탄 거리가 L이내인 점의 개수 구하기

---

접근

1. 재미난 이분탐색 문제, 어려워 보이지만 전혀 그렇지 않다. 우선 M,N이 모두 1e5이므로 O(MN)과 같이 이차항이 등장하는 순간 터진다. 최소한 O(NlogN) 수준에 풀어줘야 한다.
2. 어떤 새와 가장 가까운 사냥꾼은 어디 있을까? (x,y)에 새가 있다고 할 때, (x,0)에 있다면 가장 좋을 것이다. 그런데 없다면? x값을 사냥꾼의 위치에서 bisect해주면 된다.
3. 그리고 안전하게 구한 지점의 양 옆도 체크해주자. 체크는 아래와 같이 맨하탄 거리를 직접 구해준다.

    if (dx+y<=L)
        return 1

---

Pseudo code

int i=bisect(사냥꾼, x)
for ({i-1,i,i+1})
    if (abs(사냥꾼[i]-x)+y<=L)
        return 1

---

Source code

#include <bits/stdc++.h>
using namespace std;

#define N 100010
#define low lower_bound
int m,n,L,a[N];

bool can() {
    int x,y;
    cin>>x>>y;
    auto p=low(a,a+m,x)-a;
    for (auto q:{p-1,p,p+1})
        if (0<=q&&q<m)
            if (abs(a[q]-x)+y<=L)
                return 1;
    return 0;
}

int main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    cin>>m>>n>>L;
    for (int i=0;i<m;i++)
        cin>>a[i];
    sort(a,a+m);
    int cnt=0;
    while(n--) cnt+=can();
    cout<<cnt;
}