План – 2
Задачу добавил: alef
Успешно сдано решений: 0
Стало понятно, что на расчистку всех дорог потребуется очень много времени, а расчистка самых широких не решает главной задачи - не обеспечивает связь между всеми важнейшими объектами в городе. Оказалось, что все важнейшие объекты расположены на перекрестках дорог.
Начальник дорожной службы хотел бы узнать, сколько суммарно единиц длины дорог нужно расчистить, чтобы от любого важнейшего объекта в городе можно было бы добраться до другого.
Формат входного файла input.txt
Первая строка - целое число M (1 <= M <= 100) - количество дорог.
Каждая из следующих M строк содержит по 4 целых числа: SXq, SYq, FXq, FYq (-10000 <= SXq, SYq, FXq, FYq <= 10000, q = 1, 2, ..., M) - координаты первой и конечной точки дороги #q
Все дороги параллельны какой-либо из осей координат. Любые две дороги пересекаются не более, чем в одной точке, и каждая из дорог имеет ненулевую длину
На каждом перекрестке располагается один из важнейших объектов в городе.
Формат выходного файла output.txt
Первая строка - целое число K - суммарная длина участков дорог, которую необходимо расчистить по условию задачи.
Если решения не существует, выведите в первой строке NO SOLUTION
Пример входного файла
7
0 3 9 3
0 4 9 4
5 5 5 3
3 5 3 3
3 3 3 0
0 0 3 0
9 3 9 5
Пример выходного файла
12