Про любовь

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

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

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

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

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

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

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

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

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

Примеры

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

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