Soft_touch_plastic, Это не перебор. Это поиск кратчайшего пути в графе. Если слов всего 100 000, то можно сразу весь граф построить и гнать там хоть A*, хоть дейкстру.
Soft_touch_plastic, перебираете все варианты изменений, проверяете, что слово есть в словаре.
Если запустите какой-нибудь A*, то не надо даже граф сначала весь получать, там по ходу алгоритма просто надо обходить всех соседей вершинры - в этот момент генерируете новые слова.
voproser45654, В wingdi вы можете рисовать прямо в пиксели вашего окна. В directx работать с буфером в видеопямяти напрямую, а полноэкранном режиме вообще с пикселями на экране. Не знаю, что вам еще нужно.
profesor08, Ваше решение не верно для квадрата 1x1. Найденные 2 самые далекие точки - будут диагональю длины sqrt(2). Перпендикуляр - вторая диагональ. В итоге площадь у вас будет 2. Когда как можно пустить рамку вдоль самого квадрата, касаясть его везде - площадь будет 1.
Если ещё раз повернуть на угол А, то легко можно показать, что w2 < w1, h2 >
Вот это непонятно.
Но я по-другому доказал.
Обозначте острый угол между синей прямой и вертикальной стороной x. Площадь рамки пропорциональна sin(x)cos(c-x), где c - острый угол между синими прямыми.
Ширина рамки пропорциональна sin(x) - если провести горизонтальную высоту из левой вершины, то в прямоугольном треугольнике против угла x лежит ширина рамки. Вот и синус. Теперь надо найти острый угол между второй синей прямой и горизонтальной стороной рамки. Ясно, что этот угол будет в форме a-x. потому что поворот рамки увеличивает один острый угол и уменьшает второй. Из правого верхнего четырехугольника можно составить уравнение 360=c+(180-x)+90+(180+x-a). Отсюда a=c+90. Т.е. высота рамки пропорциональна sin(c+90-x) = cos(c-x).
Итак, площадь равна константе (длины синих отрезков) умноженной на sin(x)cos(c-x). Возьмем производную. Можно упростить как косинус разности. В итоге производная: cos(c-2x). Она равна нулю при с-2x = -90. Берем -90, потому что -180 < с-2x < 90, ведь 0 < c, x < 90. Т.е. точка экстремума вполне себе есть. Но может ли она быть минимумом? Вторая производная - 2sin(c-2x). Но мы помним, что с-2x=-90, а значит вторая производная отрицательна, а значит эта единственная точка экстремума - максимум.
ambisinister One, Ну что поделать, алгоритм сложный. В принципе, если опустить объяснение, почему это работает, да пару абзацев советов по реализации, то можно раза в 2 сократить текст. Но мне же непонятен уровень собеседника, поэтому расписывал детально.
Alexandroppolus, Если можно доказать, что ответ точно проходит через сторону, то да, можно без троичного поиска - достаточно проверить только углы вдоль сторон оболочки (и повернутые на 90, 180, 270) градусов.
Я пока не нашел контр-примера, но и доказать это я не могу.
Про поиск сделующих точек касания при сдвиге за O(1) я написал.
Без описания, что делает io_service_.run_one(), можно только догадываться. Видимо этот метод что-то как-то считает и меняеи переменную ec когда закончит.
STI1KS, Что есть? Не понял ваш коммент.
Вот, уже интереснее. Есть какая-то функция, и надо найти, где она принимает определенное значение.
И, предположительно, это значение она принимает только в одной точке. Если функция непрерывна, то это, кстати. возможно только если искомое значение - минимум или максимум функции.
Ваша изначальная функция (а не ошибка) - она непрерывна? Как она считается? Давайте все, что про нее знаете, иначе никакого вменяемого ответа вы тут не получите.
STI1KS, Можно повертеть? Сечение вдоль одной плоскости сделать? Уровни цветами задать, хотя бы? Я по этой картинке так и не могу понять, там есть локальные минимумы или нет, выпуклая ли она?
Раз вы свойства назвать не можете, давайте тогда описание, как функция считается. Какой у нее физический смысл?
Без каких либо свойств функции - действительно быстрые методы работать не будут.
Владимир Скибин, И это даст не максимальную площадь, практически всегда. Ваши треугольники всегда не будут содержать внутри других точек. Но при этом могут касаться вершинами или сторонами. Т.е какие-то точки будут висеть неиспользованными. А в оптимальном решении может надо взять большой треугольник с кучей точек внутри. Это если, как вы описали, просто выбирать максимальные треугольники. Если же выбирать их так, чтобы они не касались, то такого набора может просто не быть в триангуляции Делоне. Какое свойство именно Делоне вы используете в решении? Можно же кучей разных способов построить триангуляцию.
hint000 Это у вас итеративно выпуклая оболочка оставшегося множества откусывается как очередной слой?
Вообще можно преставить, что тругольник будет пересекать одну из оболочек в оптимальном решении. Преставьте маааленький ромб, вокруг него большой квадрат, а вокруг него еще более большой ромб. В ответе будут 4 трегуольника с вершинами из всех трех оболочек.
