Решить олимпиадную задачку на языке python 3, максимально незамысловато и быстро.
Оплата договорная

Дрону необходимо пролететь из точки start в точку finish по кратчайшему маршруту. На пути дрона встречаются препятствия, координаты которых известны и случайно генерируются перед каждым полетом.

• Препятствия представлены в виде треугольников.
• Препятствия не пересекаются и не касаются друг друга.
• Размер дрона не учитывается.
• Можно пролетать вплотную к стенам и углам препятствий.
• Высота полета не учитывается и не задается в условиях и в ответе.

Визуализация решения варианта задачи:



На вход программы поступают данные, где в первой строке указано количество последующих строк; во второй – точка start; в третьей – точка finish; в четвертой и в последующих строках – набор координат вершин препятствия (треугольника): x1 y1 x2 y2 x3 y3.

Программа должна рассчитывать и выводить координаты кратчайшего маршрута. Каждая точка маршрута указывается на новой строке. В одной строке должно быть два числа: x и y данной точки. В первой строке указывается точка start, в последней — finish.

Ответ считается верным, если:

• длина маршрута из точки start в точку finish не превышает 102% от длины кратчайшего маршрута;
• отсутствуют пересечения с препятствиями;
• первая точка соответствует точке start;
• последняя точка соответствует точке finish.

Рекомендованные библиотеки для Python: networkx для операций с графами, sympy для геометрических операций.

Sample Input 1:

6
0 95
200 40
2 134 2 131 5 3
79 134 75 75 91 114
102 105 113 136 141 128
185 2 178 102 162 33
Sample Output 1:

0 95
2 134
113 136
141 128
178 102
200 40
Sample Input 2:

6
0 37
200 74
35 6 46 48 45 65
58 21 74 139 75 47
111 32 144 141 128 61
179 77 165 39 158 130
Sample Output 2:

0 37
35 6
165 39
200 74