백준 8983 사냥꾼

문제 URL : https://www.acmicpc.net/problem/8983

8983번: 사냥꾼

 

문제접근법 :

가장명료한게 수학적으로 해결했는데요 사대의 위치에서 동물들이 L 범위에 있는지 구하는게 더어렵기때문에

동물들의 기준에서 L이내에 사대가 있는지 확인하는게 쉽습니다. 

그이유는 사대의 위치가 x축에 위치해 있기때문에 y=0 이기때문입니다

그래서 사대의 y좌표에서 L을 빼서 그에 해당하는 길이가 나옵니다. 그길이가 0보다 크면 그동물은 절대 잡히지 않습니다. 쉽게 설명을 드리자면 그림이 이해가 빠르겠지요?

y좌표가 더크기 때문에 사대위에 붕떠있음 절대 못잡음

그리고 그길이가 0혹은 음수가 나오는데 그길이의 절대값이 양옆으로 사대가 위치하면 잡힐수있는겁니다.

아래그림처럼

 

그렇다면 저사대의 위치범위를 어떻게 빠르게 찾냐? x좌표의 왼쪽기준으로 lowerbound를 사용해서

왼쪽과 오른쪽내에 위치하는 사대가있다면 잡힐수있습니다.

 

소스코드:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

//By콩순이냉장고 #include <iostream> #include <algorithm> #include <vector> #include <set> #include <cmath> using namespace std; int n, m, l; vector<int> v; set<pair<int, int>> s;   int dist(int x1, int y1, int x2, int y2) {     return abs(x1 - x2) + abs(y1 - y2); } void input() {     cin >> m >> n >> l;     v.resize(m);     for (int i = 0; i < m; i++) {         cin >> v[i];     }     for (int i = 0; i < n; i++) {         int x, y;         cin >> x >> y;         s.insert({ x,y });     } } void solve() {         sort(v.begin(), v.end());     int cnt = 0;     for (auto it = s.begin(); it != s.end();it++) {         int height = it->second-l;         if (height > 0)//붕떠있음 못잡음             continue;         height = abs(height);         int left = it->first - height;//x좌표기준으로 왼쪽         int right = it->first + height;//y좌표기준으로 오른쪽                  auto it2 = lower_bound(v.begin(), v.end(), left);         if (it2 != v.end() && left <= *it2 && *it2 <= right) {             cnt++;         }     }     cout << cnt << "\n";   } int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     input();     solve();      } Colored by Color Scripter

cs

 

궁금한점 혹은 모르는점 어떤 질문이라도 댓글은 환영입니다.