레이저
시간 제한2초메모리 제한128 MB
원점에서 뻗는 방향별로 건물을 묶어 거리순으로 정렬한 뒤, 더 가깝고 높이가 같거나 큰 건물에 레이저가 가려지는 건물을 찾는 문제입니다.
문제
2차원 평면에 N(1 <= N <= 100,000)개의 건물이 있다. 각 건물은 좌표 (x, y)에 세워져 있고 높이는 z이다. 모든 건물의 꼭대기에는 레이저가 하나씩 있으며, 레이저는 원점 (0, 0)에 있는 조각상을 향한다.
같은 반직선 위에서 조각상에 더 가까운 건물이 더 먼 건물의 레이저를 가릴 수 있다. 두 건물 A, B와 조각상이 한 직선 위에 있고, 원점에서 볼 때 B가 A보다 더 가까우며 A의 높이가 B의 높이 이하라면, A 꼭대기의 레이저는 B에 가려진다.
건물들의 좌표와 높이가 주어질 때, 레이저가 가려지는 건물의 좌표를 모두 구하라.
입력
첫째 줄에 건물의 수 N이 주어진다.
다음 N개의 줄에는 세 정수 x, y, z가 주어진다. 이는 좌표 (x, y)에 높이 z인 건물이 있다는 뜻이다.
- -100,000 <= x <= 100,000
- 0 <= y <= 10,000
- 0 <= z <= 10,000
같은 좌표에는 건물이 최대 하나만 있다.
출력
레이저가 가려지는 건물의 좌표를 한 줄에 하나씩 출력한다.
좌표는 x좌표가 증가하는 순서로 출력하고, x좌표가 같으면 y좌표가 증가하는 순서로 출력한다.