Я тренирую проблемы с кодом, и в связи с этим у меня возникают проблемы, чтобы решить их, не могли бы вы дать мне несколько советов, как их решить, пожалуйста.
Проблема взята отсюда:
https://www.ieee.org/documents/IEEEXtreme2008_Competitition_book_2.pdf
Задача 12: Циничные времена.
Проблема что-то вроде этого (но ссылка на источник проблемы приведена выше, у нее есть диаграмма!):
Ваша задача - найти последовательность точек на карте, по которой бомбардировщик должен перемещаться так, чтобы он попадал во все жизненно важные связи. Ссылка от A до B жизненно важна, когда ее отсутствие полностью изолирует A от B. Другими словами, единственный путь от A до B (или наоборот) - через эту ссылку.
Из-за контратаки противника самолету может потребоваться отступить в любой момент, поэтому самолет должен в каждый момент следовать по ближайшему жизненно важному звену, даже если в итоге общее расстояние увеличивается.
Учитывая все координаты (начальное положение самолета и узлы на карте) и диапазон R, вы должны определить последовательность положений, в которых самолет должен сбрасывать бомбы.
Эта последовательность должна начинаться (взлет) и заканчиваться (приземляться) в начальной позиции. За исключением старта и финиша, все остальные позиции должны располагаться точно в сегменте карты (то есть он должен соответствовать точке в неповрежденном жизненном сегменте ссылки).
В качестве системы координат будет использоваться UTM (универсальная поперечная проекция Меркатора) на север и восток, что в основном соответствует евклидовой перспективе мира (X = восток; Y = север).
Input
Каждый входной файл будет начинаться с трех чисел с плавающей запятой, указывающих координаты X0 и Y0 аэропорта и диапазона R. Вторая строка содержит целое число N, обозначающее количество узлов в графе дорожной сети. Тогда каждая из следующих N (<10000) строк будет содержать пару чисел с плавающей запятой, указывающих координаты Xi и Yi (1 <i <= N). Обратите внимание, что индекс i становится идентификатором каждого узла. Наконец, последний блок начинается с целого числа M, указывающего количество ссылок. Тогда каждая из следующих M (<10000) строк будет иметь два целых числа, Ak и Bk (1 <Ak, Bk <= N; 0 <k <M), которые соответствуют идентификаторам точек, которые связаны вместе. </p>
Никакие две ссылки никогда не будут пересекаться друг с другом.
Выход
Программа выведет последовательность координат (пары чисел с плавающей запятой с ровно одним десятичным знаком), каждая из которых в строке, в том порядке, в котором самолет должен посетить (начиная и заканчивая в аэропорту).
Sample input 1
102.3 553.9 0.2
14
342.2 832.5
596.2 638.5
479.7 991.3
720.4 874.8
744.3 1284.1
1294.6 924.2
1467.5 659.6
1802.6 659.6
1686.2 860.7
1548.6 1111.2
1834.4 1054.8
564.4 1442.8
850.1 1460.5
1294.6 1485.1
17
1 2
1 3
2 4
3 4
4 5
4 6
6 7
7 8
8 9
8 10
9 10
10 11
6 11
5 12
5 13
12 13
13 14
Sample output 1
102.3 553.9
720.4 874.8
850.1 1460.5
102.3 553.9