Оптимальное размещене многоугольника

[Wiedzmin]

Дан выпуклый многоугольник, нужно его разместить так (поворачивая и передвигая), чтобы в него попало наибольшее число точек с целыми значениями координат.

Координаты вершин могут быть не только на целыми (действительные)

[Azog]

Задача представляется неподъемной - скорее всего решается написанием программы, но подозреваю что за решение данной задачи - Вы рискуете получить ОЧЕНЬ серьезные деньги..

[ИСН]

(Надо же: если слово "получить" заменить на "отдать", смысл сохранится в точности)
Ну, не такая уж она и неподъёмная, перебор как перебор. Особенно если удастся найти быстрый алгоритм хотя бы для одной подзадачи:
1) максимизировать, поворачивая;
2) максимизировать, передвигая.

[Wiedzmin]

Передвижений вниз-вверх и вправо-влево для одного поворачивания кажется N^2 (N - кол-во вершин). Делаем проекции на Oy и Ox, дробные части будут нужными перемещениями. А поворачиваний - вообще трудно сказать... Интересно, можно ли использовать здесь равноотдаленность точек, чтобы уменьшить число углов для перебора?

Вообще нужно сказать нижнюю оценку сложности и построить алгоритм близкий к ней.