1. Veuillez expliquer cette solution à Rectangle Rotation sur Codesignal.com 2. Veuillez expliquer pourquoi ma solution ne fonctionne pas

Question

J'ai trouvé une solution simple que je ne comprends pas. Voici le code.

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

L'énoncé du problème est le suivant

" On dessine sur le plan cartésien un rectangle dont les côtés sont égaux à des entiers pairs a et b. Son centre (le point d'intersection de ses diagonales) coïncide avec le point (0, 0), mais les côtés du rectangle ne sont pas parallèles aux axes ; au contraire, ils forment des angles de 45 degrés avec les axes. Combien de points ayant des coordonnées entières sont situés à l'intérieur du rectangle donné (y compris sur ses côtés) ?"

J'ai essayé de résoudre le problème en utilisant sohcahtoa et j'ai écrit un tas d'équations pour les plus petites parties du rectangle, y compris l'interception des y pour les lignes supérieure et droite. J'ai calculé l'étendue valide des x en utilisant la trigonométrie. J'ai également calculé où les limites supérieures et inférieures du rectangle changent. Mon code est beaucoup plus complexe que la solution, et je comprends si les gens ne veulent pas répondre à la deuxième partie de mon problème, mais cela m'aiderait beaucoup.

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

J'obtiens une réponse qui est trop élevée pour la plupart des cas de test, et qui varie de 5 à 50 au-dessus de la réponse correcte en fonction de la valeur de a et b, plus a et b sont élevés, plus la différence est importante. Pour a = 6 et b = 4, je m'attends à une sortie de 23 mais j'obtiens 27.

Answer 1

Ne pouvons-nous pas simplement avoir une formule directe,

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

en utilisant Pythagore ?

Answer 2

Pour tenter d'expliquer le premier code, ce qui est peut-être le plus révélateur, ce sont les coordonnées énumérées que l'on retrouve dans le code. Ne le fais pas. sont pris en compte dans la solution.

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

sont les coordonnées d'un point, (x, y) tourné radians.

Si nous considérons que la diagonale du rectangle est le diamètre du cercle à l'intérieur duquel la rotation du problème se produit, nous voyons que le programme cherche à énumérer tous les points du treillis pour ce cercle tourné de 45 degrés. Ensuite, le dernier if permet de s'assurer que seuls les points de treillis tournés dans le cercle qui se trouvent à l'intérieur des limites arbitraires du rectangle sont comptés (remarquez que puisque tous les points de treillis sont énumérés, cela n'a pas d'importance si nous retournons l'instruction a y b les paramètres des côtés du rectangle, étant donné que le paramètre if restreint les coordonnées choisies par une relation fixe des deux côtés).