Задача 295
Двояковыпуклые прорези

Будем называть выпуклую область, ограниченную двумя окружностями двояковыпуклой прорезью, если:

  • Центры обеих окружностей лежат в узлах координатной сетки.
  • Две окружности пересекаются в двух отличающихся узлах координатной сетки.
  • Внутренняя часть области, ограниченной двумя окружностями, не содержит узлов координатной сетки.

Рассмотрим следующие окружности:
C0: x2 />+y2=25
C1: (x+4)2 />+(y-4)2=1
C2: (x-12)2 />+(y-4)2=65

Окружности C0, C1 и C_(2 показаны на рисунке ниже.

C0 и C_(1 образуют двояковыпуклую прорезь, равно как и C_(0 и C2.

Упорядоченную пару положительных действительных чисел (r1 />, r2) будем называть двояковыпуклой парой, если существуют две окружности радиусами r1 и r_(2, образующие двояковыпуклую прорезь. Можно убедиться, что (1, 5) и (5, √65) являются двояковыпуклыми парами для рассмотренного выше примера.

Пусть L(N) - число различных двояковыпуклых пар (r1), r2), для которых выполняется условие 0 < r 1 ≤ r2) ≤ N.
Можно убедиться, что L(10) = 30 и L(100) = 3442.

Найдите L(100 000).

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