Задача 514
Фигуры на геодоске

Геодоска (порядка N) - это квадратная доска, на поверхности которой через равные интервалы расположены штырьки, представляющие точки с целочисленными координатами на координатной сетке 0 ≤ x,yN.

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

После того, как Джон закончил генерировать числа для всех (N+1)2 отверстий и вставил все необходимые штырьки, он обтягивает тугой резинкой всю группу штырьков на доске. Пусть S обозначает образованную резинкой фигуру. S также можно определить как наименьшую выпуклую фигуру, содержащую все штырьки.

На картинке выше изображен пример доски для N = 4. Зеленые точки показывают позиции, где стоят штырьки, а совокупность синих отрезков изображает резинку. Для этого конкретного расположения площадь S равна 6. Если на доске меньше трех штырьков (или все штырьки лежат на одной прямой), площадь S считается равной нулю.

Пусть E(N) будет ожидаемой площадью S для геодоски порядка N. Например, E(1) = 0.18750, E(2) = 0.94335 и E(10) = 55.03013 при округлении до пятого знака после десятичной точки.

Рассчитайте E(100), округленное до пятого знака после десятичной точки.

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