Смотрите на картинку. Тут черными ограничены достижимые комнаты, а серым показана траетория луча из примера в задаче. Посчитайте сами - ровно 11 пересечений.
spoiler
Эта задача вообще не на геометрию - а на теорию чисел. Надо подсчитать сколько на этой треугольной решетке точек, обладающих определенными свойствами. Тут нужны делимость и взимопростота.
Если же вам интересно как смулировать луч с отражениями, то вам нужна базовая аналитическая геометрия и линейная алгебра. Нужно уметь задавать луч и отрезки параметрически, нужно знать вектора, смену системы координат, сколярное и векторное произведения.
Задайте ваш луч как p(t)=b+v*t, где b - начальная точка. v - вектор направления луча, t - параметр от 0 до бесконечности. Фактически, это 2 уравнения для X и Y: x(t)=..., y(t)=... Подставляете любое значение t, получаете точку на луче.
Изначально b - нижний угол комнаты. Потом вам надо найти, где этот луч пересечется с границей комнаты. Для этого пересеките его со всеми отрезками и найдите то пересечение, которое дает минимальное t. Задайте отрезки также параметрически (но там параметр q будет от 0 до 1). Приравняйте координаты x(t)=x(q), y(t)=y(q), решите систему 2 линейных уравнений относительно t и q. Проверьте, что значения параметров в нужных пределах.
Потом эта точка пересечения будет новым началом луча. Для отражения вектора v представьте, что мы поменяли систему координат на ту, где зеркало горизонально. Тогда отражение - просто поменять знак у координаты Y вектора v. Можно не вводить систему координат, а просто проецировать вектор v на сторону и ее нормаль через скалярное произведения и потом собрать вектор обратно сложив проекции.
Если s - вектор вдоль зеркала, n - нормаль к нему, то отраженный вектор v'=s*(v^s)/|s|-n*(v^n)/|n|. Тут "^" - это скалярное произведение. Еще вам надо будет понимать, если луч проходит через угол. Пусть этот угол - точка c. Тогда луч b+v*t проходит через нее, если (c-b)^v >=0, (c-b)*v = 0. Скалярное произведение вектора на угол и вектора луча - должно быть неотрицательно (значит вектора смотрят примерно в одну сторону). Векторное произведение должно быть 0 (значит вектора коллиниарны).
Василий Банников, это если вы точно знаете, что число в массиве есть. Тогда ceil(log n). Если же возможен ответ - не нашлось - то надо + 1 под логарифмом.
Vechnyy, Трехмерный, да. Я запутался. Посмотрите в сторону Numpy.reshape().
Ну, или вместо list comprehension делайте 3 цикла и append. Или 3 цикла по координатам и заменяйте каждый элемент отдельно, но это не очень по-питонски.
Vechnyy, Это потому что у вас массив двумерный, а я для одномерного привел. Подумайте, как можно пройтись по двумерному массиву? Или, может, превратить его в одномерный и потом назад?
KoStYaN146, первая команда может быть одной из трех: движение, ремонт и поиск (подготовку второй раз подряд делать нельзя). После движения может быть 3 варианта: движение, подготовка, поиск. После ремонта - тоже три: подготовка, движение и поиск. После поиска - только два: движение, подготовка.
Я правильно понял, что есть ограничение, что надо пройти не меньше заданного количество вершин? При этом найти минимальный из возможных путь? Что за радиус? Т.е. надо найти минимальный путь, что не менее K клеток лежат от него на расстоянии не более r?
Как у вас препятствия на карте - стены между соседними клетками, или некоторые клетки посещать нельзя? Соседей 4 или 8 (можно ли ходить по диагонали)?
Николай, Ну дак это же будет минимизировать общее количество коробок и просто выдавать math.ceil(order/9).
Ну, в некоторых случаях оно будет одну коробку заменять на что-то меньшее (если order % 18 < 6).
При чем тут НОК? Это целевая функция такая, или вы к нему пришли исходя из целевой функции.
Логично было бы минимизировать количество коробок, а потом лишнее место. Тогда задача решается так - жадно берем самую большую коробку, деля на 9 нацело. Потом, в зависимости от остатка берем или 9, или 6, или 3.
Т.е.
box[2] = order // 9
if (order % 9 > 0)
box[(order % 9 - 1)//3] += 1
tarp20, В вопросе у вас пока написано просто "в оптимальный сопосб". И никому, кроме вас непонятно, что значит - "оптимальный". Мне, например, большие коробки нравятся, потому что мой кот любит в них сидеть - поэтому любой оптимальный заказ должен содержать большую коробку. Но это мне, а что нужно в задаче - я не знаю.
Вы в сишный код передавайте массив дуг, который можно сделать тремя массивами (начало, конец и длина отдельно). А вектор векторов уже можете строить в сишном коде.
arktang, А еще V1 не подсчитать без сечегния на границы. Там, судя по рендеру, окончание - отрезок. А какой он длины? Как он расположен? V3 - нельзя подсчитать не зная под каким углом третье сечение к остальным двум. И расстояние L3 не понятно между какими точками меряется.
И пирамидой считать V2 нельзя. Только если продление сторон сойдется в точку, ибо в формуле вывода объема участвуют подобные фигуры и гарантируется, что площадь сечения посередине - среднее арифметическое сечений в концах.
А в вашем случае сечения вообще не полигонами будут - а кривыми.
Если вам нужна get_dists, то можете взять dijkstra и вернуть массив distances после цикла while. Остальной код не нужен.
Что бы 2 раза не гонять дейкстру для расстояний и пути можно вернуть одновременно массив distances и prev. Тогда по prev кодом в Dijsktra после while можно построить путь, если он нужен.
Ваш массив graph перобразуется в Graph в функции Load.
Это фактически и есть двумерый массив, но там ребра из каждой вершины сгруппированы в одну строчку.
Adamos, Как в вашем примере отсекается оптимальный вариант? Вариант "берем только первого продавца" - не отсекается, потому что он имеет минимум по всем товарам из всех взятых продавцов (он один).
Критерий не говорит, что какого-то продавца никогда не будет смысла брать потому что другие существуют. Он говорит, что не будет смысла брать его вместе с некоторыми другими.
Вот еще раз цитата:
Очевидно, что если мы берем какое-то множество продавцов, то каждый из них должен иметь минимальную цену по какому-то товару.
Смотрите на картинку. Тут черными ограничены достижимые комнаты, а серым показана траетория луча из примера в задаче. Посчитайте сами - ровно 11 пересечений.
Эта задача вообще не на геометрию - а на теорию чисел. Надо подсчитать сколько на этой треугольной решетке точек, обладающих определенными свойствами. Тут нужны делимость и взимопростота.
Если же вам интересно как смулировать луч с отражениями, то вам нужна базовая аналитическая геометрия и линейная алгебра. Нужно уметь задавать луч и отрезки параметрически, нужно знать вектора, смену системы координат, сколярное и векторное произведения.
Задайте ваш луч как p(t)=b+v*t, где b - начальная точка. v - вектор направления луча, t - параметр от 0 до бесконечности. Фактически, это 2 уравнения для X и Y: x(t)=..., y(t)=... Подставляете любое значение t, получаете точку на луче.
Изначально b - нижний угол комнаты. Потом вам надо найти, где этот луч пересечется с границей комнаты. Для этого пересеките его со всеми отрезками и найдите то пересечение, которое дает минимальное t. Задайте отрезки также параметрически (но там параметр q будет от 0 до 1). Приравняйте координаты x(t)=x(q), y(t)=y(q), решите систему 2 линейных уравнений относительно t и q. Проверьте, что значения параметров в нужных пределах.
Потом эта точка пересечения будет новым началом луча. Для отражения вектора v представьте, что мы поменяли систему координат на ту, где зеркало горизонально. Тогда отражение - просто поменять знак у координаты Y вектора v. Можно не вводить систему координат, а просто проецировать вектор v на сторону и ее нормаль через скалярное произведения и потом собрать вектор обратно сложив проекции.
Если s - вектор вдоль зеркала, n - нормаль к нему, то отраженный вектор v'=s*(v^s)/|s|-n*(v^n)/|n|. Тут "^" - это скалярное произведение. Еще вам надо будет понимать, если луч проходит через угол. Пусть этот угол - точка c. Тогда луч b+v*t проходит через нее, если (c-b)^v >=0, (c-b)*v = 0. Скалярное произведение вектора на угол и вектора луча - должно быть неотрицательно (значит вектора смотрят примерно в одну сторону). Векторное произведение должно быть 0 (значит вектора коллиниарны).