문제 풀이

반지름이 큰 순서대로 내림차순으로 정렬을 해서 배치해주고 가장 최근에 배치해준 원과 지금 배치해야하는 원이 겹치는지 안겹치는지 확인만 하면된다
정렬을 하기위해서 우선순위큐를 사용했고 일반 배열 + Sort를 사용해도 될 것이다.
가장 최근에 배치해준 원의 정보를 담기 위해서 스택을 썼는데 굳이 스택을 안써도 상관은 없다. 오히려 메모리만 더 잡아먹는 꼴이 되는듯 하지만. 그냥 사용했다.

원이 서로 겹치는지 안겹치는지는 문제에 나와있는 공식을 참고하면 된다.
겹치지 않는 조건만 PASS해주고 나머지는 겹치므로 NO를 출력하고 종료하면된다.

문제 링크

boj/22942

소스코드

PS/22942.java

    import java.util.PriorityQueue;
    import java.util.Stack;
    import java.util.StringTokenizer;


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        static class Pair implements Comparable<Pair>
        {
            int x,r;
            public Pair(int x, int r)
            {
                this.x =x;
                this.r =r;
            }

            @Override
            public int compareTo(Pair o) {
                if(this.r ==o.r)
                {
                    return this.x-o.x;
                }
                else
                    return o.r- this.r;
            }

            @Override
            public String toString() {
                return "Pair{" +
                        "x=" + x +
                        ", r=" + r +
                        '}';
            }
        }


        public static void main(String[] args) throws IOException {
            int n = Integer.parseInt(br.readLine());
            PriorityQueue<Pair> pq = new PriorityQueue<>();
            Stack<Pair> stack = new Stack<>();
            for(int i=0;i<n;i++)
            {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                pq.add(new Pair(x, r));

            }
            stack.push(pq.poll());
            while (!pq.isEmpty()) {
                int tx = stack.peek().x;
                int tr =stack.peek().r;
                int x = pq.peek().x;
                int r = pq.peek().r;
                if(r+tr<Math.abs(x-tx) || Math.abs(x-tx)< Math.abs(r-tr))
                {
                    stack.add(pq.poll());
                }
                else
                {
                    bw.write("NO");
                    bw.flush();
                    return ;
                }
            }
            bw.write("YES");
            bw.flush();
        }
    }