Laser

Time limit2sMemory limit128 MB

Summary
Group buildings by the ray from the origin, sort each group by distance, and find buildings whose laser is blocked by a closer, equally tall or taller building.
Level

Medium5 of 10

Topics
Geometry, Sorting, Hash map, Math
Solved
No attempts yet

Problem

There are N (1 <= N <= 100,000) buildings on a two-dimensional plane. A building at coordinate (x, y) has height z. A laser is installed on top of every building, and each laser points at the statue at the origin (0, 0).

A building closer to the statue can block the laser of a farther building on the same ray. If buildings A and B and the statue are collinear, B is closer to the origin than A, and A's height is less than or equal to B's height, then the laser on top of A is blocked by B.

Given the coordinates and heights of the buildings, find all buildings whose lasers are blocked.

Input

The first line contains the number of buildings N.

Each of the next N lines contains three integers x, y, and z. This means there is a building of height z at coordinate (x, y).

  • -100,000 <= x <= 100,000
  • 0 <= y <= 10,000
  • 0 <= z <= 10,000

At most one building exists at the same coordinate.

Output

Print the coordinates of all buildings whose lasers are blocked, one coordinate per line.

Print them in increasing order of x-coordinate. If two coordinates have the same x-coordinate, print them in increasing order of y-coordinate.

Examples1

  1. Example 1

    Input
    5
-1 0 1
-1 1 2
-2 2 2
-3 3 3
-4 4 2
    Expected output
    -4 4
-2 2