0063. Пересечение отрезков

Имя входного файла:	segments.in
Имя выходного файла:	segments.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Два отрезка [A, B] и [C, D] на плоскости заданы координатами своих концов – точек A, B, C, D: (X_a,Y_a), (X_b,Y_b), (X_c,Y_c), (X_d,Y_d).

Требуется найти пересечение этих отрезков и вывести:

• слово Empty, если эти отрезки не пересекаются;
• координаты точки пересечения, если пересечение состоит из единственной точки;
• координаты точек – начала и конца отрезка пересечения в лексикографическом порядке, если пересечение заданных отрезков – отрезок.

Формат входного файла

Четыре строки файла исходной информации содержат по два целых значения, по модулю не превосходящих 1000 – координаты концов точек A, B, C, D. Отрезки могут быть вырожденными.

Формат выходного файла

Числовые значения в ответе следует округлить до десяти знаков после десятичной точки.

Пример:

input.txt	output.txt
0 0 9 9 9 5 0 5	5.0000000000 5.0000000000
0 0 9 9 15 15 7 7	7.0000000000 7.0000000000 9.0000000000 9.0000000000
0 0 9 9 10 10 10 10	Empty

Источник: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Обсудить       Отправить решение



Версия для печати