EduBrick

M. Сортировка по углу

1000 мс · 256 МБ · всё или ничего

Даны точки, ни одна не совпадает с началом координат. Отсортируйте их по полярному углу - от направления оси OxOx против часовой стрелки, то есть по углу из промежутка [0,2π)[0, 2\pi). Точки с одинаковым углом упорядочьте по возрастанию расстояния до начала.

Формат ввода

В первой строке - число точек nn (1≤n≤1051 \le n \le 10^5).

В следующих nn строках - координаты точек. Координаты целые, по модулю не превосходят 10510^5; ни одна точка не совпадает с началом координат.

Формат вывода

Выведите точки в порядке возрастания полярного угла, каждую в отдельной строке. Точки с равным углом упорядочьте по возрастанию расстояния до начала координат.

Примеры

ввод
4
1 0
0 1
-1 0
0 -1
вывод
1 0
0 1
-1 0
0 -1
ввод
5
1 1
2 2
-1 0
1 0
0 -1
вывод
1 0
1 1
2 2
-1 0
0 -1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.