OSgood의 개발일기

[백준] 8983번 사냥꾼 본문

Algorithm/Algorithm 문제 연습

[백준] 8983번 사냥꾼

OSgood 2020. 3. 21. 22:29

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

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int result = 0;
long long l;
 
struct xy
{
    int x;
    int y;
};
bool getDistanc(int gun_x, xy ani)
{
    int distance = 0;
    distance = abs(gun_x - ani.x) + ani.y;
    if (distance <= l) return true;
    else return false;
}
bool comp(xy x, xy y)
{
    return x.x <= y.x;
 
}
int main()
{
    int m;
    int n;
 
 
    cin >> m >> n >> l;
 
    vector<xy> guns(m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &guns[i].x);
        guns[i].y = 0;
    }
    vector<xy> animals(n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &animals[i].x,&animals[i].y);
    }
    sort(guns.begin(), guns.end(),comp);
    sort(animals.begin(), animals.end(), comp);
 
    int leftside = 0;
    for (int j = 0; j < n; j++)//동물
    {
 
        while (leftside != m - 1 && guns[leftside + 1].x < animals[j].x)
        {
            leftside++;
        }
        if (getDistanc(guns[leftside].x, animals[j]))
        {
            result++;
            continue;
        }
        if (leftside != m - 1) {
            if (getDistanc(guns[leftside+1].x, animals[j])) {
                result++;
                continue;
            }
        }
 
    }
 
    cout << result << endl;
 
 
 
    return 0;
}
 cs

'Algorithm > Algorithm 문제 연습' 카테고리의 다른 글

[백준] 8986 전봇대  (0) 2020.03.22
[백준] 8984 막대기  (0) 2020.03.22
[백준] 10165 버스 노선  (0) 2020.03.14
[백준] 10166번 관중석  (0) 2020.03.13
[백준] 10837번 동전 게임  (0) 2020.03.13
'Algorithm/Algorithm 문제 연습' Related Articles more
Comments