|
Отрезки - 2
(Время: 3 сек. Память: 16 Мб Сложность: 52%)
Дано N отрезков на плоскости. Найдите количество пар отрезков, пересекающихся в бесконечном количестве точек (число пар перекрывающихся отрезков).
Входные данные
Входной файл INPUT.TXT содержит натуральное число N – количество отрезков (N ≤ 1000). Далее идет N строк, каждая из которых содержит четыре числа через пробел - X1, Y1, X2, Y2 – целочисленные координаты концов отрезка. Все координаты принимают значения 0 до 106. Гарантируется, что все отрезки имеют ненулевую длину.
Выходные данные
В выходной файл OUTPUT.TXT выведите количество пар перекрывающихся отрезков.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 8
1 1 2 2
2 2 3 3
1 3 3 1
10 0 20 0
20 0 30 0
15 0 25 0
50 0 100 0
70 0 80 0 | 3 |
Пояснение к примеру
Перекрываются три пары отрезков:
- [(10,0);(20,0)] и [(15,0);(25,0)] перекрываются на [(15,0);(20,0)];
- [(15,0);(25,0)] и [(20,0);(10,0)] перекрываются на [(20,0).(25,0)];
- [(50,0);(100,0)] и [(70);(80,0)] перекрываются на [(70,0).(80,0)].
Отрезки, пересекающиеся в одной точке, не перекрываются (например, [(1,1);(2,2)] и [(2,2);(3,3)]).
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
