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

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

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

B. Не курить!

Ограничение времени: 1.5 секунды
Ограничение памяти: 64 МБ
Вася — хороший парень. Но у него есть плохая привычка — он курит. Всё то время, сколько Петя дружит с Васей, он пытается отучить его от этого. Но ему это так и не удалось, потому что Вася не хочет бросать курить.
Недавно Петя придумал способ, как отучить своего друга от курения. Вася — неряха, поэтому его сигареты не лежат в пачке, а разбросаны по огромному столу. Петя хочет брать несколько сигарет в день незаметно для Васи. Вася не заметит пропажи сигарет, если в день будет пропадать не более одной сигареты. Кроме того, Петя должен брать только ту сигарету, которая пересекается с какой-нибудь другой сигаретой на столе. Помогите Пете узнать, сможет ли он начать реализацию своего плана.

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

Сигарета представляет собой отрезок ненулевой длины. В первой строке записано число N (1 ≤ N ≤ 50000) — количество сигарет на Васином столе. Следующие N строк содержат описания сигарет: (i + 1)-я строка содержит координаты концов i-й сигареты — целые числа x1, y1, x2, y2 (–10000 ≤ x1, y1, x2, y2 ≤ 10000).

Результат

В первой строке выведите слово «YES», если Пете удастся начать реализацию своего плана. Вторая строка должна содержать числа i и j: i — номер сигареты, которую должен взять Петя, j — номер сигареты, с которой она пересекается.
Если Петя не сможет взять ни одной сигареты, выведите «NO».

Примеры

исходные данныерезультат
2
0 0 2 2
0 2 2 0
YES
1 2
2
0 0 0 5
5 0 5 10
NO
Автор задачи: Илья Шишков
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1469. Не курить!