и по другой оси - после 1999-1000 будет 0-1000

тор

По идее, координаты позволяют рассчитать расстояние между любыми объектами. Расстояние между тремя городами - это треугольник, с учётом перпендикуляра - это 2 прямоугольных треугольника, где один катет общий, гипотенузы и суммы других катетов известны. Есть формула нахождения высоты в треугольнике. Находим и принимаем решение, Идти через третий город или напрямую

Что именно не точно?

Не точно определенны условия - идти через третий город чуть в стороне или напрямую (речь о промежуточных ходах). Критерий должен быть точный - когда сворачивать к третьему городу или идти напрямую

Напрямую нельзя, только через промежуточные точки

Но самым коротким путем

Только никак не могу сообразить — как определить длину перпендикуляра к прямой?

И как вообще построить перпендикуляр к прямой?

Напрямую между началом и концом, но посмотри на свой рисунок, ты же все равно не идёшь не через все точки, часть точек остаётся в стороне. Тебе нужен четкий критерий. Я его предложил. Ищи в геометрии, как найти высоту в треугольнике, когда тебе известны длИны его сторон

Напрямую между началом и концом, но посмотри на свой рисунок, ты же все равно не идёшь не через все точки, часть точек остаётся в стороне. Тебе нужен четкий критерий. Я его предложил. Ищи в геометрии, как найти высоту в треугольнике, когда тебе известны длИны его сторон

Спасибо за подсказку! Завтра буду разбираться

Спасибо за подсказку! Завтра буду разбираться

https://www-formula.ru/heighttriangle Первая формула

Если эта высота меньше половины расстояния между городами, то в этот город нужно заходить, если больше - то можно идти напрямую. И так - шаг за шагом

Или

Если расстояние от начальной точки до этой наименьшее, то заходим

А, нет..

Все, я понял!

Спасибо!

А если этот промежуточный город рядом, но в другую сторону?

Вот-вот

Спасибо!

Ещё раз посмотрел на рисунок, небольшое уточнение: заходим в промежуточный город, если высота будет меньше не половины длины, как я писал выше, а наименьшего расстояния из любого из этих двух городов до этого опущенного перпендикуляра, которое можно найти по теореме Пифагора, где нам известна гипотенуза (расстояние до промежуточного города) и один из катетов (высота)

вот код

По идее, координаты позволяют рассчитать расстояние между любыми объектами. Расстояние между тремя городами - это треугольник, с учётом перпендикуляра - это 2 прямоугольных треугольника, где один катет общий, гипотенузы и суммы других катетов известны. Есть формула нахождения высоты в треугольнике. Находим и принимаем решение, Идти через третий город или напрямую

а разве это не будет просто полный граф?

Ещё раз посмотрел на рисунок, небольшое уточнение: заходим в промежуточный город, если высота будет меньше не половины длины, как я писал выше, а наименьшего расстояния из любого из этих двух городов до этого опущенного перпендикуляра, которое можно найти по теореме Пифагора, где нам известна гипотенуза (расстояние до промежуточного города) и один из катетов (высота)

Да, так будет лучше! Спасибо

а разве это не будет просто полный граф?

Что значит в данном случае - полный граф? С точки зрения расстояния нам проще пройти напрямую из точки А в точку Б, как решить эту задачу с помощью теории графов, если дороги есть между любыми двумя городами? На мой взгляд, условие слишком расплывчатое. Следует ли считать решением путь в обход, который по длине будет намного дольше, но с минимальным расстояниями между городами (хотя этих сегментов будет много)?

Если да, тогда можно решить помощью теории графов

Привет!

Что значит в данном случае - полный граф? С точки зрения расстояния нам проще пройти напрямую из точки А в точку Б, как решить эту задачу с помощью теории графов, если дороги есть между любыми двумя городами? На мой взгляд, условие слишком расплывчатое. Следует ли считать решением путь в обход, который по длине будет намного дольше, но с минимальным расстояниями между городами (хотя этих сегментов будет много)?

города - узлы графа, расстояния между узлами - вес ребер... ищем кратчайший путь между двумя узлами

ребру между А и Б можно задать заведомо большой вес, чтоб игнорировать этот путь

Здесь только задачи решают? Или можно задавать вопрос на другие темы?

На любые можно

полный граф - это граф у которого каждый узел соединен с каждым другим узлом

Ок, спасибо.

https://pastebin.com/mhHPQz4f кто разбирается в авторизации - вопрос к вам.

не могу авторизоваться на сайте. Что делаю не так?

Неужели это граббер гикбрейнс?

граббер - это что?

ребру между А и Б можно задать заведомо большой вес, чтоб игнорировать этот путь

Тогда будет выгоден заход в один город, который ближе всех к прямой между А и Б.

прочитал про граббер ) нет это не он, хочу научиться синхронизировать календарь занятий с календарем гугла, но не могу пройти авторизацию. Уже около месяца мучаюсь, но все никак

ребру между А и Б можно задать заведомо большой вес, чтоб игнорировать этот путь

Возможно стоит искать путь с наименьшим значением максимального расстояния (веса) в пути, не взирая на количество сегментов

Тогда будет выгоден заход в один город, который ближе всех к прямой между А и Б.

ну, если пространство Евклидово - то да

Я уже жаловался на то, что точных критериев в задании нет

но я так понимаю, из информации о городах только расстояния между ними?

Судя по всему, даны двумерные координаты городов (как я понял)

опять же, на геодезической поверхности или на плоскости )

Я думаю, что задача абстрактна, рассматривается плоскость, иначе мы уйдем в рельеф местности, водные преграды и т.п.

Я думаю, что задача абстрактна, рассматривается плоскость, иначе мы уйдем в рельеф местности, водные преграды и т.п.

нашел изначальные условия тут... там задача в виде графа и поставлена

Ребята, помогите с задачей. Есть список с координатами вершин графа: points = [(0,0),(12,55)(51,51)...] Необходимо взять две рандомные вершины из этого списка и найти между ними самый короткий путь по другим вершинам. Результат вывести в виде списка path, где path[0] == начальная точка, а path[-1] == конечная точка

Есть всякого рода функции типа quote() для преобразования текста в "нормальный" вид

Т.е. по всем другим вершинам? Разновидность задачи коммивояжера?

Ребята, помогите с задачей. Есть список с координатами вершин графа: points = [(0,0),(12,55)(51,51)...] Необходимо взять две рандомные вершины из этого списка и найти между ними самый короткий путь по другим вершинам. Результат вывести в виде списка path, где path[0] == начальная точка, а path[-1] == конечная точка

т.е. задача просто на поиск кратчайшего пути графа

не могу авторизоваться на сайте. Что делаю не так?

Сделай селениумом, проще будет

да

Сделай селениумом, проще будет

Делал, норм авторизовал, но дальше не знаю че с ним делать, хочу реквестом

Вот что бывает, когда читаешь условие, пересказанное своими словами )

Т.е. по всем другим вершинам? Разновидность задачи коммивояжера?

мне кажется это именно она и есть

Не помню, если ли в оригинальной задаче условие финала в определенном городе. По-моему, там просто объехать все города кратчайшим способом. Могу ошибаться

Значит надо просто отобрать все пути, которые кончаются в точке Б

Нет, это не задача комивояджера

ERROR: S client not available

Задача расплывчата, но то что подсказал Сергей — подходит)

в любом случае, для питона полно библиотек для решения графов

Последний критерий прям то что мне нужно было

Я так думаю

Завтра проверю

Эм

Вы все решаете?

Теперь такая ошибка появилась

Задача расплывчата, но то что подсказал Сергей — подходит)

min(points, key=lambda x: distance(x,a)+distance(x,b)) Так не катит?

min(points, key=lambda x: distance(x,a)+distance(x,b)) Так не катит?

Не

Код покажи

Теперь такая ошибка появилась

Слишком мало данных, чтобы понять причину, нужен исходный код

Явно ведь документацию не читал

Слишком мало данных, чтобы понять причину, нужен исходный код

urllib.request.urlopen('https://api.telegram.org/bot'+str(token)+'/editMessageReplyMarkup?chat_id='+str(from_id)+'&message_id='+str(message_id))+'&reply_markup='+str(keyboard_inline) Такой запрос token - токен для доступа к апи Проблема кроется в keyboard_inline Русские символы не нравятся, англ норм

Господи

Зачем ты так урл формируешь?

Потому что полез в телеграм прежде чем выучить питон

Прежде чем документацию прочитал и про экранирование узнал

Зачем ты так урл формируешь?

А как?

urllib.request.urlopen('https://api.telegram.org/bot'+str(token)+'/editMessageReplyMarkup?chat_id='+str(from_id)+'&message_id='+str(message_id))+'&reply_markup='+str(keyboard_inline) Такой запрос token - токен для доступа к апи Проблема кроется в keyboard_inline Русские символы не нравятся, англ норм

params = urlencode({'q': text_to_read}) connection = urllib.request.urlopen("http://www.wdylike.appspot.com/?" + params)

Первый же пример со stackoverflow

Urlencode тебе поможет

Так тоже делал, я решил все прописать в запросе

Ну и зря решил

И вообще взял бы requests либу

Так тоже делал, я решил все прописать в запросе

ну во-первых это неправильно, так как ты не экранируешь URL query.

  The Requests package is recommended for a higher-level HTTP client interface

Говорит нам документация

а во-вторых ^ requests

Говорит нам документация

дык это ж надо еще документацию читать.