반응형
https://www.acmicpc.net/problem/8983
8983번: 사냥꾼
입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
vector<int> gun;
bool distance(int x, int y, int L) {
bool ans = false;
if (y > L) return false;
int s = 0;
int e = gun.size() - 1;
while (s <= e) {
int mid = (s + e) / 2;
if (abs(gun[mid] - x) + y <=L) {
ans = true;
break;
}
else if (gun[mid] > x) {
e = mid - 1;
}
else {
s = mid + 1;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m, n, l;
cin >> m >> n >> l;
for (int i = 0; i < m; i++) {
int tmp;
cin >> tmp;
gun.push_back(tmp);
}
sort(gun.begin(), gun.end());
int cnt = 0;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
if (distance(x, y ,l)) cnt++;
}
cout << cnt << '\n';
return 0;
}
반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 2458번 : 키 순서 - 플로이드 와샬 알고리즘 (0) | 2022.02.17 |
|---|---|
| 백준 2610: 회의준비 - 플로이드–와샬 C++ (0) | 2022.02.16 |
| 백준 6087번 : 레이저 통신 - 다익스트라 C++ (0) | 2022.02.16 |
| 백준 2108번: 통계학 C++ (0) | 2022.02.16 |
| 백준 9370번 : 미확인 도착지 - 다익스트라 (0) | 2022.02.15 |