https://www.acmicpc.net/problem/8983
8983번: 사냥꾼
KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x1, x2, ..., xM은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a1, b1), (a2, b2), ..., (aN, bN)과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다. 사냥꾼이
www.acmicpc.net
문제해설
이 문제는 "라인스위핑(line sweeping)" 알고리즘을 사용하여 해결 할 수 있습니다.
어떤 축을 기준으로 정렬한뒤에, 확인하는 경우의수를 대폭 줄일 수 있습니다.
많은 다른 블로그들은 lower_bound 없이 반복문으로 O(N)으로 풀으셨는데
lower_bound를 사용 하여 O(NlgN) 으로 풀었습니다.
풀이는 다음과 같습니다.
사대를 x축 정렬
동물들도 x축 정렬
정렬된 동물들을 처음부터 끝까지 탐색하는데
해당 동물이 사냥될 수 있는지 체크하기 위해서
해당 동물과 가장 오른쪽에서 가까운(x축기준) 사대
해당 동물과 가장 왼쪽에서 가까운(x축기준) 사대
를 찾아서 거리를 구해주면 됩니다.
lower_bound의 예외처리를 쉽게 하기 위해서 밑과 같은 사전처리를 해주었습니다.
sands.push_back(-MAX);
sands.push_back(MAX);
전체코드
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
vector<ll> sands;
vector<pair<ll, ll> > ani;
ll getDist(ll x, ll x1, ll y1) {
return abs(x - x1) + y1;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int M, N, L; cin >> M >> N >> L;
ll MAX = 1000000001;
for (int i = 0; i < M; i++) {
ll x; cin >> x;
sands.push_back(x);
}
for (int i = 0; i < N; i++) {
ll x, y; cin >> x >> y;
ani.push_back({ x,y });
}
sands.push_back(-MAX);
sands.push_back(MAX);
sort(sands.begin(), sands.end());
sort(ani.begin(), ani.end());
int ans = 0;
for (int i = 0; i < ani.size(); i++) {
ll x = ani[i].first;
ll y = ani[i].second;
auto left = lower_bound(sands.begin(), sands.end(), x);
auto right = left - 1;
if (min(getDist(*right, x, y), getDist(*left, x, y)) <= L) ans++;
}
cout << ans;
}