1. 请解释 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 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))

使用毕达哥拉斯？

Answer 2

为了尝试解释第一个代码，更能说明问题的可能是不计算在解决方案中的枚举坐标。

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

是一个点的坐标，(x, y)，旋转了 θ 弧度。

如果我们认为矩形的对角线是发生问题旋转的圆的直径，我们会看到程序试图枚举旋转 45 度的圆的所有格点。然后最后的 if 语句确保只计算落在矩形任意边界内的圆中那些旋转的格点（注意，由于所有格点都被枚举，所以我们是否翻转 a 和 b，矩形边的参数，因为 if 语句通过与两边的固定关系来限制所选坐标。

1. 请解释 Codesignal.com 上的矩形旋转的解决方案 2. 请解释为什么我的解决方案不起作用

1. Please explain this solution to Rectangle Rotation on Codesignal.com 2. Please explain why my solution doesn't work

algorithm

trigonometry