|
Олимпиады прошлых лет
|
||||||||||||||||||||||||||||||
|
Олимпиада проводится при поддержке Компьютерного супермаркета "НИКС" и компании Genius
Информационная поддержка:
журнал "Мир ПК"
II Всероссийская заочная олимпиада школьников по информатике, 2007/08 учебный год
Задача F. Найдите прямую
| Имя входного файла: | f.in |
| Имя выходного файла: | f.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
На плоскости дано N горизонтальных отрезков. Будем говорить, что прямая пересекает отрезок, если у этой прямой и этого отрезка есть хотя бы одна общая точка (в том числе прямая пересекает отрезок, если она проходит через один из его концов). Требуется найти прямую, пересекающую все отрезки, или установить, что такой нет.
Формат входных данных
В первой строке входного файла находится единственное число N. В каждой из следующих N строк содержатся по три целых числа Pi, Qi, Ri, описывающих отрезки: соответствующий отрезок соединяет точки (Pi, Ri) и (Qi, Ri). Никакие два отрезка не лежат на одной прямой.
1≤N≤10000, Pi<Qi, все числа по модулю не превосходят 10000.
Формат выходных данных
В случае, если искомая прямая существует, выведите в выходной файл коэффициенты ее уравнения (будем задавать прямую уравнением вида Ax+By+C=0, г де x, y - координаты точек прямой, A, B, C - такие коэффициенты, что указанному уравнению удовлетворяют все точки прямой, и только они; соответственно, чтобы задать прямую, нужно задать три числа - A, B, C).
Коэффициенты уравнения должны быть целыми и не должны превосходить по модулю 109 (гарантируется, что при наличии решения такие A, B, C существуют).
Если прямой не существует, выведите в выходной файл сообщение "No solution" (без кавычек).
Примеры
| f.in | f.out |
3 0 1 0 0 1 1 0 1 2 |
1 0 0 |
5 0 2 0 2 4 1 1 3 2 1 3 -1 1 3 -2 |
3 -1 -5 |
3 0 1 0 1 2 1 -2 -1 2 |
No solution |