Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Про любовь

(Время: 1 сек. Память: 16 Мб Сложность: 70%)

Ваське нравится Машка. Она симпатичная, и он очень любит смотреть на нее. Но ему нравится и Ленка! Она тоже довольно симпатичная. Васька может смотреть на нее часами, когда она сидит на скамейке и читает книгу. Почему бы не подойти и поговорить с ней? Есть небольшая проблема. Васька - кот.

Но надо сказать, что это его не очень беспокоит. В общем, он даже привык к этому. Ему просто нравится смотреть на девочек. К сожалению, часто дома и другие препятствия не дают увидеть обеих девочек одновременно. А даже когда это можно сделать, найти подходящую точку довольно сложно. Васька просит вас, своего любимого хозяина, помочь ему.

Даны положения препятствий и точки, в которых находятся девочки. Найдите точку, из которой видны обе девочки, или установите, что такой точки нет. Конечно, Васька не может забираться внутрь препятствий.

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа x1 и y1 - координаты Машки. Следующая строка содержит x2 и y2 - координаты Ленки. Третья строка входного файла содержит n - количество препятствий (0 ≤ n ≤ 10).

Все препятствия являются прямоугольниками со сторонами, параллельными осям координат. Каждая из следующих n строк содержит четыре целых числа xi,1, yi,1, xi,2 и yi,2 – координаты левого нижнего и правого верхнего углов препятствий. Все координаты не превосходят 100 по абсолютному значению. Препятствия не пересекаются, но могут касаться друг друга. Если два препятствия касаются друг друга углами или сторонами, между ними нет зазора. В противном случае Васька может смотреть таким образом, что линия его взгляда касается угла или идет вдоль стороны препятствия.

Ни одна из девочек не находится внутри или на границе какого-то из препятствий. Девочки находятся в разных точках.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите «YES» , если точка, из которой Васька может видеть обеих девочек, существует. В этом случае вторая строка должна содержать два вещественных числа - координаты точки, из которой должен смотреть Васька. Эта точка не должна быть внутри какого-либо препятствия, но может быть на его границе. Васька не должен находиться в точке, которая одновременно принадлежит углам двух зданий, не имеющих общей стороны. Координаты должны быть выведены с точностью не менее, чем 10-6. Если искомой точки нет, выведите «NO» в единственную строку выходного файла.

Примеры

INPUT.TXTOUTPUT.TXT
12 0
-2 0
1
-1 -2 1 2
YES
0.0 4.0
22 0
-2 0
3
-1 -1 1 1
-3 -3 -1 -1
-3 1 1 3
NO

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483