WebDev, даже код на php иногда можно ускорить в сотни раз, если использовать правильный алгоритм и структуры данных. Это с запасом покроет медленность этого решения на пхп против быстроты тупого решения на встроенных функциях.
Да, такой же код на си будет в несколько раз быстрее, но если у вас нет возможности переписать все или только сложную часть на си, то придется довольствоваться этим.
mIka01, Напишите все-таки, что за триангуляцию вам надо. Пока под условие подходит вернуть пустой массив, или {{1,2,3},{4,5,6},...}. Тоже триангуляции.
Вам точно триангуляция Делоне нужна или вам просто разбить на тругольники без пересечений, чтобы все точки были состояли в треугольниках?
jcmvbkbc, Просто повторение фраз из стандарта, без какой-либо попытки их осмыслить, обычно плохо кончаются (второй пример там).
Стандарт лишь говорит, что нет никакого UB, и вычисления производятся по модулю 2^n. В русском языке термина для "underflow" особо нет, поэтому я использовал слово "переполнение".
Если проблема "чтобы не было отрицательных значений" - то предлагать unsigned - это весьма необдуманное решение.
jcmvbkbc, Проблема ТС в том, что x%m при отрицательном m выдаст неверное, отрицательное число. Да, с тем же остатком, но в вычислениях нужно число от 0 до m-1. Правильное решение этой проблемы - прибавить m, если число отрицательно, или всегда прибавлять m и брать по модулю опять. ТС же, наобум вставил модуль. Если же тупо заменить все переменные на unsigned int, то там будет переполнение и, фактически, прибавление 2^32 к ответу. Что тоже испортит ответ, если только m - не степень двойки.
fronttrty, Давайте сначала. Запишите формулу хеша на отрезке l..r. Запишите формулу для каждого prefhash и powp. Запишите как ваш getshash считает, приравняйте, посмотрите, то ли у вас получилось.
Mark, Можно эту же логику сделать на сервере. Или для каждого клиента считайте, сколько раз он уже посылал запрос и был послан, или считайте, сколько было отказов всем клиентам в какое-то окно времени.
При посыле клиента подождать реализуйте экспоненциальный откат - генерите случайное число ожидания в промежутке, зависящим от счетчика отказов (для данного клиента или в целом по серверу).
Mark, Сервер, если не может обработать запрос сразу отвечает клиенту "я занят". Клиент, если получает от сервера это, или таймаут или ошибку запроса - откатывается.
Смотрите на картинку. Тут черными ограничены достижимые комнаты, а серым показана траетория луча из примера в задаче. Посчитайте сами - ровно 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, Это потому что у вас массив двумерный, а я для одномерного привел. Подумайте, как можно пройтись по двумерному массиву? Или, может, превратить его в одномерный и потом назад?
Попробуйте константы поднять. 20 соседей - возможно мало. Длина очередей может быть, вообще говоря, любой в этом решении.