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

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

Два отрезка [A, B] и [C, D] на плоскости заданы координатами своих концов – точек A, B, C, D: (Xa,Ya), (Xb,Yb), (Xc,Yc), (Xd,Yd).

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

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

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

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

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

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

Пример:

input.txtoutput.txt
0 0 9 9 9 5 0 55.0000000000 5.0000000000
0 0 9 9 15 15 7 77.0000000000 7.0000000000 9.0000000000 9.0000000000
0 0 9 9 10 10 10 10Empty


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

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



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