Решить олимпиадную задачку на языке 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 33Sample Output 1:
0 95 2 134 113 136 141 128 178 102 200 40Sample 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 130Sample Output 2:
0 37 35 6 165 39 200 74