1. Пожалуйста, объясните это решение для Rectangle Rotation на Codesignal.com 2. Пожалуйста, объясните, почему мое решение не работает

Question

Я нашел простое решение, которое я не понимаю.Вот код.

def rectangleRotation(a, b):
    pt = 0
    radius = pow(a/2,2)+pow(b/2,2)
    radius = int(math.ceil(pow(radius,.5)))

    for i in range(-radius,radius+1):
        for j in range(-radius,radius+1):
            x = i*math.cos(math.radians(-45)) - j*math.sin(math.radians(-45))
            y = i*math.sin(math.radians(-45)) + j*math.cos(math.radians(-45))
            if -a/2<=x<=a/2 and -b/2<=y<=b/2:
                pt += 1
    return pt

Задача:

"Прямоугольник со сторонами, равными четным целым числам a и b, нарисован на декартовой плоскости. Его центр (точка пересечения его диагоналей) совпадает с точкой (0, 0), но стороны прямоугольника не параллельны осям, вместо этого они образуют углы в 45 градусов с осями. Сколько точек с целочисленными координатами находится внутризаданный прямоугольник (в том числе на его сторонах)? "

Я попытался решить проблему с помощью sohcahtoa и написал несколько уравнений для меньших частей прямоугольника, включая пересечение y для верхнего исамые правые линии.Я рассчитал действительный диапазон х, используя триг.Я также рассчитал, где меняется верхняя и нижняя граница прямоугольника.Мой код намного сложнее, чем решение, и я понимаю, что люди не хотят отвечать на вторую часть моей проблемы, но это мне очень поможет.

int rectangleRotation(int a, int b) {
    // let y1 be the y intercept for the upper line of the rectangle     
    double y1 = b/sqrt(2);
    // let y2 be the y intercept for the right line of the rectangle
    double y2 = a/sqrt(2);
    // let xyrange be the ceil of the range of x and y
    int xyrange = floor((sqrt(2)/4)*(a + b));
    // let x1 be the point at which the lower/upper line changes
    double x1 = (sqrt(2)/4)*(a - b);
    // let points be the number of points within the rectangle
    int points = 0;
    for (int i = -xyrange; i <= xyrange; i++) {
        // let ru be the floor of upper line value of the rectangle at i
        double ru;
        // check if the upper line changed
        if (i >= ceil(x1)) {
            ru = -i + y2;
        } else {
            ru = i + y1;
        }
        // let rui be the integer bound for the upper line
        int rui;
        if (ru <= 0) {
            rui = ceil(ru);
        } else {
            rui = floor(ru);
        }
        // let rl be the ceil of lower line value of the rectangle at i
        double rl;
        // check if the lower line changed
        if (i <= -floor(x1)) {
            rl = -i - y2;
        } else {
            rl = i - y1;
        }
        // let rui be the integer bound for the upper line
        int rli;
        if (rl <= 0) {
            rli = ceil(rl);
        } else {
            rli = floor(rl);
        }
        for (int j = -xyrange; j <= xyrange; j++) {
            if (j <= rui && j >= rli) {
                points++;
            }
        }
    }
    return points;
}

Я получаю ответ, который является слишком высоким для большинства тестовых случаев и варьируется от 5 до 50 над правильным ответом в зависимости от значений a и b, чем выше a и b, тем большеразница есть.Для a = 6 и b = 4 я ожидаю выхода 23, но получаю 27.

Answer 1

Чтобы попытаться объяснить первый код, возможно, более показательны перечисленные координаты, которые не засчитываются в решение.

x' = x cos(θ) - y sin(θ)
y' = x sin(θ) + y cos(θ)

- это координаты дляточка, (x, y), повернутая θ радиан.

Если мы считаем, что диагональ прямоугольника - это диаметр круга, в котором происходит вращение задачи, мы видим, что программа стремится перечислить все точки решеткидля этого круга повернут на 45 градусов.Затем последнее утверждение if проверяет, будут ли учитываться только те повернутые точки решетки в окружности, которые попадают в произвольные границы прямоугольника (обратите внимание, что, поскольку все точки решетки перечислены, не имеет значения, если мы перевернем a иb, параметры сторон прямоугольника, поскольку оператор if ограничивает выбранные координаты фиксированным отношением к обеим сторонам).

Answer 2

Разве мы не можем иметь прямую формулу,

function f(a, b){
  let big = Math.max(a, b)
  let small = Math.min(a, b)

  let NE_x_y = Math.floor(Math.sqrt(big * big / 8))
  let width = 2 * NE_x_y + 1
  let half_height = Math.floor(Math.sqrt(small * small / 8))
  let height = 2 * half_height + 1

  let rectangle_1 = width * height

  let hypotenuse = Math.sqrt(2 * NE_x_y * NE_x_y) + 1 / Math.sqrt(2)

  let rectangle_2_w

  if (hypotenuse <= big / 2)
    rectangle_2_w = width + 1
  else
    rectangle_2_w = width - 1

  let rectangle_2_h = 2 * (Math.floor((small / 2 - 1/Math.sqrt(2)) / Math.sqrt(2)) + 1)

  return rectangle_1 + rectangle_2_w * rectangle_2_h
}

console.log(f(6, 4))

с использованием Пифагора?