algorithm - 1. 请在 Codesignal.com 上解释一下 Rectangle Rotation 的这个解决方案 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 rectangle with sides equal to even integers a and b is drawn on the Cartesian plane. Its center (the intersection point of its diagonals) coincides with the point (0, 0), but the sides of the rectangle are not parallel to the axes; instead, they are forming 45 degree angles with the axes. How many points with integer coordinates are located inside the given rectangle (including on its sides)?"

我尝试使用 sohcahtoa 解决问题，并为矩形的较小部分写下了一堆方程式，包括上面和最右边的线的 y 截距。我使用 trig 计算了有效的 x 范围。我还计算了矩形上下边界变化的位置。 我的代码比解决方案复杂得多，我理解如果人们不想回答我问题的第二部分，但这会对我有很大帮助。

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;
}

我得到的答案对于大多数测试用例来说都太高了，根据 a 和 b 的值，正确答案从 5 到 50 不等，a 和 b 越高，差异越大。对于 a = 6 和 b = 4，我期望输出为 23，但我得到了 27。

Answer 1

我们不能直接有一个公式吗，

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))

使用毕达哥拉斯？