images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
05/12/2025 14:59:17

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

145. Плоттер

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

Плоттер – это устройство для рисования чертежей и карт, позволяющее чертить на листе бумаги отрезки прямых с помощью специального пера. Чертеж может состоять из многих тысяч линий, и некоторые из них при комбинировании плоттер мог бы нарисовать одним отрезком. Напишите программу, которая объединяет в один отрезок отрезки, расположенные на одной прямой и накладывающиеся друг на друга или хотя бы соприкасающиеся, и минимизирует таким образом число рисуемых отрезков на чертеже.
В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 2500`) – количество отрезков. Далее следует `N` строк, в каждой строке содержатся четыре вещественных числа, разделенных пробелами – координаты одного конца отрезка `(x_1,\ y_1)`, затем координаты другого конца отрезка `(x_2,\ y_2)`. Координаты лежат в диапазоне от 0 до 1000 и заданы с не более чем двумя десятичными знаками. Отрезки имеют ненулевую длину.
В выходной файл вывести строку, содержащую одно целое число – минимальное количество отрезков, которое нужно начертить плоттеру после оптимизации чертежа.

Пример ввода 1

3
1.0 10.0 3.0 14.0
0.0 0.0 20.0 20.0
10.0 28.0 2.0 12.0

Вывод для примера 1

2

Пример ввода 1

2
0.0 0.0 1.0 1.0
1.0 1.0 2.15 2.15

Вывод для примера 1

1
loading