데이터 체커

Description

원점과 반지름의 형태로 원 N개가 주어진다.

원 N이 서로 교점을 가지고 있는지 없는지 판단하여야 한다.

TRY

1. n^2을 이용한 풀이 - TLE
2. 인접한 원의 중심끼리 연산하려했음. [반례존재]
   • 2번째 원에서 1번째, 3번째 원과는 겹치지 않는 상황(2번째원이 1,3번째 원 내접)인 경우, 3번째가 1번째와 교점을 만들 수 있는 상황이 연출될 수 있음.
3. 스택과 큐를 이용한 풀이
   • 큐 안에는 각 원들의 반지름으로 부터 왼쪽, 오른쪽 좌표가 들어 가있음.
   • 각 안에 있는 점들은 각 원에 대한 고유한 id를 가지고 있음.
   • 정렬을 하고 스택에 id를 넣게 되면 같은 번호의 다른 점이 들어올 수 있음
   • id가 같다는 이야기는 즉, 다른 원과의 교점없이 해당 범위에는 나만 있음을 증명할 수 있음.
4. 각 원에있는 왼쪽,오른쪽 점을 각각 큐에 넣어 x축 기준으로 정렬하고 스택에 id를 넣음.

Solution

static class Point implements Comparable<Point> {
		int id;
		int x; //(왼쪽 점 또는 오른쪽 점)

		public Point(int id, int x) {
			this.id = id;
			this.x = x;
		}

		public int compareTo(Point o) {
			return this.x - o.x;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Point> pq = new PriorityQueue<>();
		int n = Integer.parseInt(reader.readLine());
		for (int id = 0; id < n; id++) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
			int mid = Integer.parseInt(tokenizer.nextToken());
			int r = Integer.parseInt(tokenizer.nextToken());

			Point left = new Point(id, mid - r);
			Point right = new Point(id, mid + r);

			pq.offer(left);
			pq.offer(right);
		}
		Stack<Integer> s = new Stack<>();
		while (!pq.isEmpty()) {
			if (s.isEmpty()) {
				s.push(pq.poll().id);
			} else {
				int id = pq.poll().id;

				if (s.peek() == id) {
					s.pop();
				} else {
					s.push(id);
				}
			}
		}

		System.out.println(s.isEmpty() ? "YES" : "NO");
	}