IPB
ЛогинПароль:

> 

Начальные контакты ТОЛЬКО через личку!!

> олимпиадная информатика. Вычислительная геометрия. Найти прямую.
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 1
Пол: Мужской

Репутация: -  0  +


Максимальное время работы на одном тесте: 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" (без кавычек).
Примеры
{input}
3
0 1 0
0 1 1
0 1 2
{output}
1 0 0
{input}
5
0 2 0
2 4 1
1 3 2
1 3 -1
1 3 -2
{output}
3 -1 -5

{input}
3
0 1 0
1 2 1
-2 -1 2
{output}
No solution

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 3)
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Откуда задача?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Отсюда, вестимо...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Вот и отличненько.

tototot, попробуй, пожалуйста, воровать в другом месте.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 4:20
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name