Wataru

Готовых решений я не знаю, но есть следующие идеи.

Во-первых, научимся аппроксимировать одной кривой. Первая и четвертая точки нам известны - это первый и последний пиксель. координаты двух других опорных точек кривой Безье - это четыре неизвестных.

Составим функцию ошибки f(x1, y1, x2, y2) = (X(i/n)-x_i)^2+(Y(i/n)-y_i)^2. Тут x_i, y_i - координаты i-ого пикселя в нарисованной кривой, пронумерованные от 0 до n, X(t), Y(t) - координаты точки на кривой Безье - линейные комбинации x1, x2 и y1, y2 с известными вычисляемыми от t коэффициентами. Это фактически сумма квадратов расстояний от каждого пикселя до неизвестной кривой. Ее можно минимизировать подобно методу наименьших квадратов - считайте производную по всем переменным, приравнивайте к 0. Получите 4 неизвестные и 4 линейных уравнения. Можно вообще на бумажке руками методом Краммера решить, а можно алгоритмом Гаусса подсчитать.

Тут есть допущение, что i-ый пиксель будет аппроксимироваться t=i/n точкой на кривой. Вообще говоря, это не гарантированно, но в качестве некой грубой меры оптимальности подойдет. Может вообще отлично работать будет и так, я не знаю. Поэксперементируйте. Но еще можно потом честно искать ближайшую точку на кривой к заданному пикселю как оптимум полинома 6-ей степени от t, когда все опорные точки кривой фиксированы. Тут надо брать производную, находить ее нули и среди них брать лучшее t. Чтобы найти нули полинома 5-ой степени можно рекурсивно брать производную, находить нули полинома меньшей степени, и потом на каждом монотонном отрезке искать пересечение с OX бинарным поиском. Или использовать метод Ньютона. Это давно решенная задача - должно быть куча готовых решений.

Когда вы так научились считать расстояние от кучки пикселей до кривой Безье, можно локально градиентным спуском по 4-м координатам x1, x2, y1, y2 улучшать эту правильную метрику с оптимума полученного грубой метрикой.

Вот мы и умеем аппроксимировать кучку пикселей одной кривой. Заодно мы получаем метрику близости кривой к пикселям. Но надо сделать ее не зависящей от длины - поэтому складывайте квадраты расстояний и делите на количество пикселей.

А дальше алгоритм прост - жадно откусывайте от вашего массива пикселей самые длинные куски, которые хорошо аппроксимируются кривой (дают маленькую метрику). Для этого можно тупо перебирать сколько пикселей отдаем первой кривой, считать метрику и, если она слишком плохая, то останавливаться. Можно чем-то вроде бинарного поиска тут делать - увеличиваете длину куска в 2 раза, пока метрика не станет плохой, а потом гоните бинарный поиск, ища самое большое значение количество пикселей, которое еще дает хорошую метрику. (тут используется предположение, что чем короче пиксельная кривая, тем легче ее аппроксимировать).

Это эмпирический алгоритм и он много где жадный. Нет никакой гарантии, что он даст математически оптимальный результат, но есть много шансов, что он даст достаточно хороший результат.

Готов поклястся, что именно этот вопрос был задан вот тут.

Но вы же, видимо, его и отредактировали, а теперь спрашиваете опять. Ответ там уже был мной дан.

Во-первых, если скорости маленькие и движение происходит на маленькие отрезки за итерацию, то можно выталкивать объект в любую сторону.

Если же шаги не настолько мелкие, то нужно, как уже подсказал Фокс Йовович, сдвигать до пересечения, а не впихивать объект в другой и выталкивать назад.

Есть концептуально простой но далеко не самый эффективный метод - бинарный поиск. Вот вы уже умеете определять, пересекаются ли 2 объекта. Изначально они не пересекались, после сдвигания на 1.0 едениц веремени они пересеклись. Делайте бинарный поиск по времени в отрезке (0, 1): посморите, есть ли пересечение при сдвиге на 0.5 единиц времени. Потом или 0.25 или 0.75 в зависимости от результата проверки. И так пока текущий отрезко в бинпоиске не станет достаточно мал. Но у этого метода большая проблема с большими скоростями - если за время итерации объекты пройдут сквозь друг друга - вы этого не заметите.

Более быстрый метод - это реально искать пересечение тракетории. Для этого пустите лучи из каждой вершины одного объекта параллельные его скорости движения относительно второго объекта. Потом пересеките каждый луч со вторым многоугольником и найдите кратчайший луч. Аналогично надо пустить лучи из всех вершин второго многоугольника в обратную сторону и пересечь их все с первым многоугольником (это если движущийся наткнется на вершину препятствия стороной). Нашли длину минимального луча - на нее и сдвигайтесь. Если задавать лучи параметрически в виде point+t*v, то фактически вы ищете минимальное значение параметра t при пересечении у всех лучей (тут v - вектор скорости за один квант времени,point - вектор координат точки, из который выпустили луч).

В этом методе не надо даже проверять, попадает ли после полного шага объект в препятствие. Нашли минимальное расстояние до пересечения (может быть и бесконечностью, если пересечений нет) - если оно больше сдвига за квант времени, то сдвигайтесь просто на квант времени. в параметрическом подходе, это значит, что сдвигаетесь вы на min(1.0, t).

Этот метод можно соптимизировать с квадратичного до линейного. Представьте, что вектор движения горизонтален (и направлен влево). Можно просто повернуть все точки каждого многоугольника вместе со всем пространством или применять векторные/скалярные произведения для определения, какая точка ниже/левее/правее.

Найдите в каждом многоугольнике самую нижнюю и самую верхнюю точку. Если эти промежутки по OY не пересекаются - то два объекта не столкнутся, можно останавливать проверки. Если промежутки по OY пересекаются, но второй обхект находится правее первого - то они отдаляются и опять можно дальше не проверять. Тут можно сравнить по одной любой точке с каждого объекта.

Потом, как в алгоритме слияния двух отсортированных массивов, берете 2 указателя на 2 самые нижние точки в объектах. В левом объекте указатель будет двигаться против часовой стрелки, а в правом - по. Так вы будете обходить лицевые стороны объектов. Смотрите, какая из двух точек ниже. Пускаете луч из нее и пересекаете с одним отрезком - выходящим из текущей точки на втором многоугольнике вверх, и только с ним. Сдвигаете указатель с той самой нижней точки на следующую. Отстанавливаетесь, когда дошли до обеих высших точек.

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

Можно его до сублинейного соптимизировать через бинарный поиск опять, но тут уже очень сложно. Можно низшую и высшую точки искать за логарифм бинпоиском, а не как выше полным перебором всех точек. Потом тернарным поиском перебираете значение координаты Y и считаете расстояние между двумя многоугольниками вдоль этого горизонтального отрезка. Для этого, опять же бинпоиском, находите 2 отрезка пересекающих эту горизонталь в обоих многоуголниках и пересекаете с горизонталью, чтобы найти 2 конца расстояния. Эта функция расстояния dist(y) будет выпуклой. Поэтому уможно найти ее минимум тернарным поиском.

n=5, m=1. первый шаг - поделить, осталось n=1, m=0. Второй шаг - проверить, заметить 0 и остановиться.

n=5,m=3, первый шаг - поделить. осталось n=3, m=2. Второй шаг - опять делим, остается m=2, n=1. Третий шаг - делим, остается n=1, m=0, четвернтый шаг - видим 0, остановились.

для n=m=5 ответ 1, возможно, потому что в алгоритме стоит проверка m==0 || m == n.

Это похоже на задачу set cover. Легких алгоритмов тут нет. Только полный перебор с отсечениями. Еще всякие методы отжига и эволюционные алгоритмы могут найти хорошее решение. Ну и, задачу можно переформулировать в виде integer linear programming и решать какой-то из существующих библиотек.

Если количество слов маленькое (типа 25-30), то можно решать динамическим программированием по маске покрытых слов.

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

Если он указывает на "E" и встретил 0, куда он будет указывать после поворота? На "N".
Аналогично, в обратную сторону, при указывании на " N" после 1, он будет указывать на "E".

Чему это соответствует в вашем массиве a? Что происходит с индексом?

Лень разбираться в вашем коде, но на кой черт там вообще замена? Эта задача решается потоково - прочитали символ из входной строки, добавили от 0 до 4-х символов выходную строку. Можно еще сначала один раз пройтись и подсчитать длину в ответа, если жалко 3*strlen(input) заводить. Длина ответа - 3*(k-1) + c, где k - количество слов, а с - количество непробельных символов.

Главное наблюдение - любое слово начинается с непробельного символа, перед которым идет пробельный (или начало строки).

Соответственно решение вообще тупое - прочитали непробельный символ - если он начало слова, вывели 3 пробела. В любом случае вывели этот непробельный символ. Если прочитали пробельный символ - пропустили его (ну или флаг установили для упрощения кода в первом случае).

Берете бумажку, рисуете на ней нужный вам спиральный массив. Внимательно на нее смотрите.

Выписываете прямые куски - какой они длины, в какую сторону вращаются. Ищите паттерн (например в спиральном массиве из центра длины кусков: 1, 1, 2, 2, 3, 3, ...).

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

Для реализации поворота храните текущее направление в виде двух переменных dx, dy. Одна из них +-1, а другая 0. Для поворота против часовой стрелки делаете (dx, dy) = (-dy, dx)

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

Быстрые алгоритмы есть: Кнута-Морриса-Пратта, Бойера-Мура. Там есть примеры реализации алгоритма в википедии прямо кодом на Си. Эти алгоритмы сканируют строку текст посимвольно. Эту часть нужно тупо заменить вводом очередного символа из файла (не забудьте сделать буферизацию, если ваш ЯП этого не делает сам).

Ну, или, если файл не большой, то можно тупо прочитать весь файл в строку и запустить какой-нибудь встроенный метод поиска подстроки в строке. Большинство ЯП уже реализуют какой-либо быстрый метод поиска.

Для поворота достаточно перед SetPixel повернуть xu и yu на угол, пропорциональный прошедшему времени. Ну или количеству тиков, но лучше по таймеру ориентироваться.

Чтобы окно перерисовывалось периодически само надо делать как тут: запустить таймер на несколько миллисекунд и по его срабатыванию перерисовывать окно. Можно или как в этом примере стирать и рисовать заново, а можно вызывать WM_PAINT через какой-нибудь RedrawWindow:

RedrawWindow(hWnd, NULL, NULL, RDW_INVALIDATE | RDW_UPDATENOW);