Encontrar el rectángulo de mejor ajuste que cubre un punto dado

Posted on by Rudeus Greyrat

Disponemos de un plano 2D y un punto ( X ,  Y ). Tenemos que encontrar un rectángulo ( X_1 ,  Y_1 ,  X_2 ,  Y_2 ) tal que
abarque el punto dado ( X ,  Y ). El rectángulo elegido debe satisfacer la condición dada  \frac{largo}{ancho}=\frac{a}{b} . Si
son posibles varios rectángulos, debemos elegir el que tenga la menor distancia Euclidiana entre el centro del rectángulo y el punto ( X ,  Y ). 
 

Fuente de la imagen – Codeforces  
Ejemplos: 
 

Input : 70 10 20 5 5 3
Output :12 0 27 9

Input :100 100 32 63 2 41
Output :30 18 34 100

La lógica detrás del problema es la siguiente. En primer lugar, reducimos  \frac{a}{b} a la forma irreducible más baja dividiendo a y b por  mcd(a, b) . Pensamos en el problema en dos dimensiones separadas  X e  Y independientes. Hallamos el  min(n/a, m/b) después de dividir a y b por su mcd para encontrar la distancia máxima que podemos cubrir con seguridad permaneciendo en el rango de  (0, 0) a (n, m) . Dado que tenemos que encontrar un rectángulo con una distancia mínima de su centro desde el punto ( X ,  Y ), comenzamos con la suposición de que el punto ( X ,  Y ) es nuestro centro. Luego encontramos  X_1 y  X_2 restando y sumando la mitad de la longitud a  X . Si cualquiera  X_1 o  X_2 sale del rango, cambiamos las coordenadas en consecuencia para traerlo dentro del rango (0, 0) a (n, m) . Del mismo modo procedemos a calcular  Y_1 y  Y_2 . 
Para el primer ejemplo, de acuerdo con la lógica anterior, la respuesta resulta ser  12, 0, 27, 9 .
 

C++

#include <cmath>
#include <iostream>
using namespace std;
 
// Function to calculate
// GCD of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    else
        return gcd(b % a, a);
}
 
// Function to calculate the
// coordinates of the rectangle
void solve(int n, int m, int x, int y, int a, int b)
{
 
    int k, g;
    int x1, y1, x2, y2;
    g = gcd(a, b);
 
    // Reducing the ratio to
    // lowest irreducible form
    a /= g;
    b /= g;
 
    // Finding the maximum multiple
    // of length that can be chosen
    k = min(n / a, m / b);
 
    // Assuming the point (X, Y) as the
    // centre of the required rectangle
    // Finding the lower X coordinate by
    // subtracting half of total length from X
    x1 = x - (k * a - k * a / 2);
 
    // Finding the upper X coordinate
    // by adding half of total length to X
    x2 = x + k * a / 2;
 
    // Finding lower Y coordinate by
    // subtracting half of breadth from Y
    y1 = y - (k * b - k * b / 2);
 
    // Finding upper Y coordinate
    // by adding half of breadth to Y
    y2 = y + k * b / 2;
 
    // If lower X coordinate
    // goes below 0 then we shift
    // the lower coordinate to 0
    // and the upper coordinate
    // accordingly to bring lower
    // coordinate in range
    // and to keep center as
    // close as possible to X, Y
    if (x1 < 0) {
        x2 -= x1;
        x1 = 0;
    }
 
    // If upper X coordinate goes
    // beyond n, then we shift the
    // upper X coordinate ton
    // and we shift the lower coordinate
    // accordingly to bring the upper
    // coordinate in range
    if (x2 > n) {
        x1 -= x2 - n;
        x2 = n;
    }
 
    // If lower Y coordinate goes
    // below 0 then we shift the
    // lower coordinate to 0
    // and the upper coordinate
    // accordingly to bring lower
    // coordinate in range
    // and to keep center as
    // close as possible to X, Y
    if (y1 < 0) {
        y2 -= y1;
        y1 = 0;
    }
 
    // If upper Y coordinate goes
    // beyond n, then we shift the
    // upper X coordinate
    // to n and we shift the lower
    // coordinate accordingly to
    // bring the upper
    // coordinate in range
    if (y2 > m) {
        y1 -= y2 - m;
        y2 = m;
    }
 
    cout << x1 << " " << y1 << " " << x2
         << " " << y2 << endl;
}
 
// Driver function
int main()
{
    int n = 70, m = 10, x = 20, y = 5, a = 5, b = 3;
    solve(n, m, x, y, a, b);
    return 0;
}

Java

class GFG {
 
    // Function to calculate
    // GCD of a and b
    public static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        else
            return gcd(b % a, a);
    }
 
    // Function to calculate the
    // coordinates of the rectangle
    public static void solve(int n, int m,
                             int x, int y,
                             int a, int b)
    {
 
        int k, g;
        int x1, y1, x2, y2;
        g = gcd(a, b);
 
        // Reducing the ratio to
        // lowest irreducible form
        a /= g;
        b /= g;
 
        // Finding the maximum multiple
        // of length that can be chosen
        k = Math.min(n / a, m / b);
 
        // Assuming the point (X, Y) as the
        // centre of the required rectangle
        // Finding the lower X coordinate by
        // subtracting half of total length
        // from X
        x1 = x - (k * a - k * a / 2);
 
        // Finding the upper X coordinate
        // by adding half of total length
        // to X
        x2 = x + k * a / 2;
 
        // Finding lower Y coordinate by
        // subtracting half of breadth
        // from Y
        y1 = y - (k * b - k * b / 2);
 
        // Finding upper Y coordinate
        // by adding half of breadth
        // to Y
        y2 = y + k * b / 2;
 
        // If lower X coordinate
        // goes below 0 then we shift
        // the lower coordinate to 0
        // and the upper coordinate
        // accordingly to bring lower
        // coordinate in range
        // and to keep center as
        // close as possible to X, Y
        if (x1 < 0) {
            x2 -= x1;
            x1 = 0;
        }
 
        // If upper X coordinate goes
        // beyond n, then we shift the
        // upper X coordinate ton
        // and we shift the lower coordinate
        // accordingly to bring the upper
        // coordinate in range
        if (x2 > n) {
            x1 -= x2 - n;
            x2 = n;
        }
 
        // If lower Y coordinate goes
        // below 0 then we shift the
        // lower coordinate to 0
        // and the upper coordinate
        // accordingly to bring lower
        // coordinate in range
        // and to keep center as
        // close as possible to X, Y
        if (y1 < 0) {
            y2 -= y1;
            y1 = 0;
        }
 
        // If upper Y coordinate goes
        // beyond n, then we shift the
        // upper X coordinate
        // to n and we shift the lower
        // coordinate accordingly to
        // bring the upper
        // coordinate in range
        if (y2 > m) {
            y1 -= y2 - m;
            y2 = m;
        }
 
        System.out.println(x1 + " " + y1 + " " + x2
                           + " " + y2);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int n = 70, m = 10;
        int x = 20, y = 5;
        int a = 5, b = 3;
        solve(n, m, x, y, a, b);
    }
}
 
// This code is contributed by - vkz6198

Python 3

# Function to calculate
# GCD of a and b
def gcd(a, b):
 
    if (a == 0):
        return b
    else:
        return gcd(b % a, a)
 
# Function to calculate the
# coordinates of the rectangle
def solve(n, m, x, y, a, b):
 
    g = int(gcd(a, b))
 
    # Reducing the ratio to
    # lowest irreducible form
    a /= g
    b /= g
 
    # Finding the maximum multiple
    # of length that can be chosen
    k = int(min(n / a, m / b))
 
    # Assuming the point (X, Y) as the
    # centre of the required rectangle
    # Finding the lower X coordinate by
    # subtracting half of total length
    # from X
    x1 = int(x - (k * a - k * a / 2))
 
    # Finding the upper X coordinate
    # by adding half of total length
    # to X
    x2 = int(x + k * a / 2)
 
    # Finding lower Y coordinate by
    # subtracting half of breadth from Y
    y1 = int(y - (k * b - k * b / 2))
 
    # Finding upper Y coordinate
    # by adding half of breadth to Y
    y2 = int(y + k * b / 2)
 
    # If lower X coordinate
    # goes below 0 then we shift
    # the lower coordinate to 0
    # and the upper coordinate
    # accordingly to bring lower
    # coordinate in range
    # and to keep center as
    # close as possible to X, Y
    if (int(x1) < 0):
        x2 -= x1
        x1 = 0
     
 
    # If upper X coordinate goes
    # beyond n, then we shift the
    # upper X coordinate ton
    # and we shift the lower coordinate
    # accordingly to bring the upper
    # coordinate in range
    if (int(x2) > n):
        x1 -= x2 - n
        x2 = n
     
 
    # If lower Y coordinate goes
    # below 0 then we shift the
    # lower coordinate to 0
    # and the upper coordinate
    # accordingly to bring lower
    # coordinate in range
    # and to keep center as
    # close as possible to X, Y
    if (int(y1) < 0) :
        y2 -= y1
        y1 = 0
     
 
    # If upper Y coordinate goes
    # beyond n, then we shift the
    # upper X coordinate
    # to n and we shift the lower
    # coordinate accordingly to
    # bring the upper
    # coordinate in range
    if (int(y2) > m):
        y1 -= y2 - m
        y2 = m
     
 
    print(x1 , " " , y1 , " " , x2
        , " " , y2,sep="")
 
# Driver function
n = 70
m = 10
x = 20
y = 5
a = 5
b = 3
solve(n, m, x, y, a, b)
 
# This code is contributed by Smitha

C#

using System;
 
class GFG {
 
    // Function to calculate
    // GCD of a and b
    public static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        else
            return gcd(b % a, a);
    }
 
    // Function to calculate the
    // coordinates of the rectangle
    public static void solve(int n, int m,
                            int x, int y,
                            int a, int b)
    {
 
        int k, g;
        int x1, y1, x2, y2;
        g = gcd(a, b);
 
        // Reducing the ratio to
        // lowest irreducible form
        a /= g;
        b /= g;
 
        // Finding the maximum multiple
        // of length that can be chosen
        k = Math.Min(n / a, m / b);
 
        // Assuming the point (X, Y) as the
        // centre of the required rectangle
        // Finding the lower X coordinate by
        // subtracting half of total length
        // from X
        x1 = x - (k * a - k * a / 2);
 
        // Finding the upper X coordinate
        // by adding half of total length
        // to X
        x2 = x + k * a / 2;
 
        // Finding lower Y coordinate by
        // subtracting half of breadth
        // from Y
        y1 = y - (k * b - k * b / 2);
 
        // Finding upper Y coordinate
        // by adding half of breadth
        // to Y
        y2 = y + k * b / 2;
 
        // If lower X coordinate
        // goes below 0 then we shift
        // the lower coordinate to 0
        // and the upper coordinate
        // accordingly to bring lower
        // coordinate in range
        // and to keep center as
        // close as possible to X, Y
        if (x1 < 0) {
            x2 -= x1;
            x1 = 0;
        }
 
        // If upper X coordinate goes
        // beyond n, then we shift the
        // upper X coordinate ton
        // and we shift the lower coordinate
        // accordingly to bring the upper
        // coordinate in range
        if (x2 > n) {
            x1 -= x2 - n;
            x2 = n;
        }
 
        // If lower Y coordinate goes
        // below 0 then we shift the
        // lower coordinate to 0
        // and the upper coordinate
        // accordingly to bring lower
        // coordinate in range
        // and to keep center as
        // close as possible to X, Y
        if (y1 < 0) {
            y2 -= y1;
            y1 = 0;
        }
 
        // If upper Y coordinate goes
        // beyond n, then we shift the
        // upper X coordinate
        // to n and we shift the lower
        // coordinate accordingly to
        // bring the upper
        // coordinate in range
        if (y2 > m) {
            y1 -= y2 - m;
            y2 = m;
        }
 
        Console.Write(x1 + " " + y1 +
                 " " + x2 + " " + y2);
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 70, m = 10;
        int x = 20, y = 5;
        int a = 5, b = 3;
        solve(n, m, x, y, a, b);
    }
}
 
// This code is contributed by Smitha

PHP

<?php
// Function to calculate
// GCD of a and b
 
function gcd($a, $b)
{
    if ($a == 0)
        return $b;
    else
        return gcd($b % $a, $a);
}
 
// Function to calculate the
// coordinates of the rectangle
function solve($n, $m, $x, $y, $a, $b)
{
 
    $k; $g;
    $x1; $y1; $x2; $y2;
    $g = gcd($a, $b);
 
    // Reducing the ratio to
    // lowest irreducible form
    $a /= $g;
    $b /= $g;
 
    // Finding the maximum multiple
    // of length that can be chosen
    $k = min($n / $a, $m / $b);
 
    // Assuming the point (X, Y)
    // as the centre of the required
    // rectangle Finding the lower
    // X coordinate by subtracting
    // half of total length from X
    $x1 = $x - ($k * $a - $k * $a / 2);
 
    // Finding the upper X
    // coordinate by adding
    // half of total length to X
    $x2 = $x + $k * $a / 2;
 
    // Finding lower Y coordinate by
    // subtracting half of breadth from Y
    $y1 = $y - ($k * $b - $k * $b / 2);
 
    // Finding upper Y coordinate
    // by adding half of breadth to Y
    $y2 = $y + $k * $b / 2;
 
    // If lower X coordinate
    // goes below 0 then we shift
    // the lower coordinate to 0
    // and the upper coordinate
    // accordingly to bring lower
    // coordinate in range
    // and to keep center as
    // close as possible to X, Y
    if ($x1 < 0)
    {
        $x2 -= $x1;
        $x1 = 0;
    }
 
    // If upper X coordinate goes
    // beyond n, then we shift the
    // upper X coordinate ton
    // and we shift the lower coordinate
    // accordingly to bring the upper
    // coordinate in range
    if ($x2 > $n)
    {
        $x1 -= $x2 - $n;
        $x2 = $n;
    }
 
    // If lower Y coordinate goes
    // below 0 then we shift the
    // lower coordinate to 0
    // and the upper coordinate
    // accordingly to bring lower
    // coordinate in range
    // and to keep center as
    // close as possible to X, Y
    if ($y1 < 0)
    {
        $y2 -= $y1;
        $y1 = 0;
    }
 
    // If upper Y coordinate goes
    // beyond n, then we shift the
    // upper X coordinate
    // to n and we shift the lower
    // coordinate accordingly to
    // bring the upper
    // coordinate in range
    if ($y2 > $m)
    {
        $y1 -= $y2 - $m;
        $y2 = $m;
    }
 
    echo $x1, " ", $y1, " ",
         $x2, " ", $y2, "\n";
}
 
// Driver Code
$n = 70; $m = 10; $x = 20;
$y = 5; $a = 5; $b = 3;
solve($n, $m, $x, $y, $a, $b);
 
// This code is contributed by aj_36
?>

Javascript

<script>
    // Function to calculate
    // GCD of a and b
    function gcd(a, b)
    {
        if (a == 0)
            return b;
        else
            return gcd(b % a, a);
    }
   
    // Function to calculate the
    // coordinates of the rectangle
    function solve(n, m, x, y, a, b)
    {
   
        let k, g;
        let x1, y1, x2, y2;
        g = gcd(a, b);
   
        // Reducing the ratio to
        // lowest irreducible form
        a = a / g;
        b = b / g;
   
        // Finding the maximum multiple
        // of length that can be chosen
        k = Math.min(parseInt(n / a, 10), parseInt(m / b, 10));
   
        // Assuming the point (X, Y) as the
        // centre of the required rectangle
        // Finding the lower X coordinate by
        // subtracting half of total length
        // from X
        x1 = x - (k * a - k * parseInt(a / 2, 10));
   
        // Finding the upper X coordinate
        // by adding half of total length
        // to X
        x2 = x + k * parseInt(a / 2, 10);
   
        // Finding lower Y coordinate by
        // subtracting half of breadth
        // from Y
        y1 = y - (k * b - k * parseInt(b / 2, 10));
   
        // Finding upper Y coordinate
        // by adding half of breadth
        // to Y
        y2 = y + k * parseInt(b / 2, 10);
   
        // If lower X coordinate
        // goes below 0 then we shift
        // the lower coordinate to 0
        // and the upper coordinate
        // accordingly to bring lower
        // coordinate in range
        // and to keep center as
        // close as possible to X, Y
        if (x1 < 0) {
            x2 -= x1;
            x1 = 0;
        }
   
        // If upper X coordinate goes
        // beyond n, then we shift the
        // upper X coordinate ton
        // and we shift the lower coordinate
        // accordingly to bring the upper
        // coordinate in range
        if (x2 > n) {
            x1 -= x2 - n;
            x2 = n;
        }
         
        x1 += 1; x2 += 1;
   
        // If lower Y coordinate goes
        // below 0 then we shift the
        // lower coordinate to 0
        // and the upper coordinate
        // accordingly to bring lower
        // coordinate in range
        // and to keep center as
        // close as possible to X, Y
        if (y1 < 0) {
            y2 -= y1;
            y1 = 0;
        }
   
        // If upper Y coordinate goes
        // beyond n, then we shift the
        // upper X coordinate
        // to n and we shift the lower
        // coordinate accordingly to
        // bring the upper
        // coordinate in range
        if (y2 > m) {
            y1 -= y2 - m;
            y2 = m;
        }
   
        document.write(x1 + " " + y1 + " " + x2 + " " + y2);
    }
     
    let n = 70, m = 10;
    let x = 20, y = 5;
    let a = 5, b = 3;
    solve(n, m, x, y, a, b);
     
</script>

Producción : 
 

12 0 27 9

Publicación traducida automáticamente

Artículo escrito por HGaur y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *