ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2015

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Друзья и ягоды

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Есть компания из n ребят. Как гласит народная мудрость, на вкус и цвет товарищей нет. Вот и ребята не сошлись в оценке вкусовых качеств клубники и малины. А именно, i-й оценивает свою любовь к клубнике как si, а к малине — как ri.
Другая народная мудрость гласит, что противоположности притягиваются. И, как ни странно, больше сдружились те ребята, чьи вкусы не совпадают.
Дружественностью между парой людей v, u назовем число: p(v, u) = sqrt((svsu)2 + (rvru)2)
Дружественностью тройки людей v, u, w назовем полусумму попарных дружественностей: p(v,u,w) = (p(v,u) + p(v,w) + p(u,w)) / 2
Лучшие друзья — это такая пара людей, что вдвоем им не хуже, чем с кем-либо еще. Формально скажем, что v, u — лучшие друзья, если vu и p(v, u) ≥ p(v,u,w) для любого w. Нужно найти все пары лучших друзей.

Исходные данные

В первой строке записано одно целое число n — количество ребят (2 ≤ n ≤ 2 · 105).
Затем в n строках записаны по два целых числа в каждой — si и ri (−108si, ri ≤ 108).
Гарантируется, что нет двух ребят с абсолютно одинаковыми предпочтениями. Иными словами, если vu, то либо svsu, либо rvru.

Результат

В первой строке выведите количество пар лучших друзей.
Затем выведите все эти пары по одной в строке — для каждой пары номера ребят, которые в неё входят, через пробел. Ребята нумеруются с единицы в порядке, в котором они описаны во входных данных. Пары и номера ребят внутри пар можно выводить в любом порядке.
Гарантируется, что количество пар не превосходит 105.

Примеры

исходные данныерезультат
2
2 3
7 6
1
1 2
3
5 5
2 -4
-4 2
0
Автор задачи: Алексей Данилюк (подготовка — Алексей Данилюк, Александр Борзунов)
Источник задачи: Уральская региональная командная олимпиада по программированию 2015
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2067. Друзья и ягоды