时间戳

首页 > 解决方案 > 1. 请在 Codesignal.com 上解释这个解决方案 Rectangle Rotation 2. 请解释为什么我的解决方案不起作用

algorithm - 1. 请在 Codesignal.com 上解释这个解决方案 Rectangle Rotation 2. 请解释为什么我的解决方案不起作用

问题描述

我找到了一个我不明白的简单解决方案。这是代码。

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) 重合，但矩形的边不平行于“

我尝试使用 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。

标签： algorithmtrigonometry

解决方案

难道我们不能有一个直接的公式，

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

使用毕达哥拉斯？

推荐阅读