Найдите оптимальный обрезанный круг ⇐ Python

[Гость]

Данная матрица целых чисел размером n на n, я хочу найти обрезанный круг, который максимизирует сумму. Вот изображение, а затем последует объяснение/код:

Код: Выделить всё

      [[ 1,  1, -3,  0,  0,  3, -1,  3, -3,  2],
[-2, -1,  0,  1,  0, -2,  0,  0,  1, -3],
[ 2,  2, -3,  2, -2, -1,  2,  2, -2,  0],
[-2,  0, -3,  3,  0,  2, -1,  1,  3,  3],
[-1, -2, -1,  2,  3,  3, -3, -3,  2,  0],
[-3,  3,  2,  0, -3, -2, -1, -3,  0, -3],
[ 3,  2,  2, -1,  0, -3,  1,  1, -2,  2],
[-3,  1,  3,  3,  0, -3, -3,  2, -2,  1],
[ 0, -3,  0,  3,  2, -2,  3, -2,  3,  3],
[-1,  3, -3, -2,  0, -1, -2, -1, -1,  2]]

Центр круга находится в точке (0,0), и нас интересует только та часть, которая пересекает сетку. В каждой целочисленной координате в сетке находится целое число. Круг может иметь любой радиус (не обязательно целочисленный, но об этом ниже).
Существует также диагональная линия, которая может обрезать круг, как показано на рисунке. Диагональная линия всегда начинается и заканчивается в целочисленной координате на границе сетки и идет вниз и вправо под углом 45 градусов к горизонтали, как показано на рисунке.
Оценка за обрезанный круг — это сумма всех целых чисел, которые находятся как внутри круга (или на границе), так и на стороне диагональной линии, включая (0,0). Значения на границе (или рядом с ней): -3, 1, 3, -1, -3, 3, -1, 2, 0, 3.
Хотя круг может имеют любой радиус, нам нужно рассматривать только круги, которые точно пересекают точку сетки, чтобы существовало n ^ 2 различных соответствующих радиуса. Кроме того, нам нужно записать только одну позицию, где круг пересекается с диагональной линией, чтобы полностью указать обрезанный круг. Обратите внимание, что это пересечение с диагональю не обязательно должно происходить по целочисленной координате.
Если в оптимальном решении диагональ вообще не отсекает круг, то нам нужно только вернуть радиус. круга.
Если бы мы хотели найти только оптимальный круг, мы могли бы сделать это быстро и за время, пропорциональное входному размеру, с помощью:

Код: Выделить всё

import numpy as np
from math import sqrt
np.random.seed(40)

def find_max(A):
n = A.shape[0]
sum_dist = np.zeros(2 * n * n, dtype=np.int32)
for i in range(n):
for j in range(n):
dist = i**2 + j**2
sum_dist[dist] += A[i, j]
cusum = np.cumsum(sum_dist)
# returns optimal radius with its score
return sqrt(np.argmax(cusum)), np.max(cusum)
A = np.random.randint(-3, 4, (10, 10))
print(find_max(A))

Как быстро можно найти оптимальную обрезанную окружность?

Подробнее здесь: https://stackoverflow.com/questions/781 ... ped-circle