[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼

문제 >> 백준 8389 사냥꾼   /   정올 2635 사냥꾼

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//정올 2364 사냥꾼
//백준 8983 사냥
//2019-03-05
 
public class Main_8983{
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        int M = Integer.parseInt(st.nextToken()); // 사대 수
        int N = Integer.parseInt(st.nextToken()); // 동물 수
        long L = Integer.parseInt(st.nextToken()); // 사정거리
        int ans = 0;
        long yy = Long.MIN_VALUE;
        long xx = Long.MIN_VALUE;
        long[] gun = new long[M+1];
        pair[] animal = new pair[N];
        st = new StringTokenizer(bf.readLine(), " ");
        for (int i = 0; i < M; i++) {
            int token = Integer.parseInt(st.nextToken());
 
            gun[i] = token;
        }
        gun[M] = 1000000001;
        Arrays.sort(gun);
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
             
 
            animal[i] = new pair(x, y);
        }
        Arrays.sort(animal);
 
        /*
         * gun과 animal의 좌표를 x를 기준으로 정렬한다. 
         * animal을 기준으로 두고, gun을 순회한다. 
         * gun의 처음부터 순회하다가 사정거리 안에 포함되는 사대를 발견했을 때, 카운트 해주고 사대의 시작 위치를 바꿔준다. 
         * 다음 동물은 현재 사대부터 보면 된다 .
         */
 
        int cur = 0;
        for (int i = 0; i < N; i++) {
            pair p = animal[i];
            int ax = p.x;
            int ay = p.y;
            if (ay > L || ax < gun[0] - L ) continue;
            
            //animal의 x좌표가 gun의 최대  최대 범위보다 커지는 경우 그 이후의 좌표는 탐색하지 않아도 된다.
            if (ax > gun[M - 1] + L) break;
 
            for (int j = cur; j < M; j++) { // 사대 검사
                long dist = getDist(gun[j],ax,ay);
                if(dist<=L) {
                    ans++;
                    cur = j;
                    break;
                }
                //사정거리안에 없으면서 gun의 x값이 크면 break
                if(ax<gun[j]) break;
 
            }
 
        }
 
        System.out.println(ans);
    }
 
    public static long getDist(long x, int a, int b) {
        return Math.abs(x - a) + b;
    }
 
    static class pair implements Comparable<pair> {
        int x;
        int y;
 
        public pair(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
 
        @Override
        public int compareTo(pair o) {
            // TODO Auto-generated method stub
            return this.x-o.x;//오름차순 
        }
    }
}