Задача 742
Минимальная площадь выпуклого многоугольника на сетке

Симметричный выпуклый многоугольник на сетке - это такой многоульник, у которого:

  • все вершины имеют целочисленные координаты,
  • все внутренние углы строго меньше $180°$,
  • присутствует вертикальная и горизонтальная симметрия.

Например, левый многоугольник является выпуклым многоугольником на сетке, но он не обладает ни горизонтальной, ни вертикальной симметрией. В свою очередь, правый многоугольник является истинным симметричным выпуклым многоугольником с 6 вершинами на сетке:

Определим $A(N)$ как минимальную площадь симметричного выпуклого многоугольника с $N$ вершинами на сетке.

Известно, что $A(4) = 1$, $A(8) = 7$, $A(40) = 1039$ и $A(100) = 17473$.

Найдите $A(1000)$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net