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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | 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;//오름차순 } } } | cs |
'Algorithm Problem Solving' 카테고리의 다른 글
| [SWEA] 7236 : 저수지의 물의 총 깊이 구하기 (1) | 2019.03.07 |
|---|---|
| [SWEA] 1861 : 정사각형 방 (0) | 2019.03.07 |
| [BOJ] 1012 : 유기농배추 (1) | 2019.02.17 |
| [BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰) (2) | 2019.02.17 |
| [SWEA] 2819 격자판의 숫자 이어 붙이기 (0) | 2019.02.16 |
