Finding the best fit rectangle that covers a given point
We are provided with a 2D plane and a point (
, ). We have to find a rectangle (, , , ) such that it
encompasses the given point (, ). The rectangle chosen must satisfy the given condition . If
multiple rectangles are possible the we must choose the one with the least Euclid distance between the center of the rectangle and the point (, ).
Image Source – codeforces
Examples :
Input : 70 10 20 5 5 3
Output :12 0 27 9Input :100 100 32 63 2 41
Output :30 18 34 100
The logic behind the problem is as follows. First of all we reduce to lowest irreducible form by dividing a and b by . We think of the problem in two separate dimensions and independently. We find out the after dividing a and b by their gcd to find the maximum distance that we can cover safely by staying in the range of . Since we have to find rectangle with minimum distance of its center from the point (, ), therefore we start with the assumption that point (, ) is our center. Then we find and by subtracting and adding half of length to . If either or goes out of range then we shift the coordinates accordingly to bring it inside the range . Similarly we proceed to calculate and .
For the first example according to above logic the answer comes out to be .
C++
#include <cmath>#include <iostream>using namespace std;// Function to calculate// GCD of a and bint gcd(int a, int b){ if (a == 0) return b; else return gcd(b % a, a);}// Function to calculate the// coordinates of the rectanglevoid 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 // center 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 functionint 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 bdef gcd(a, b): if (a == 0): return b else: return gcd(b % a, a)# Function to calculate the# coordinates of the rectangledef 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 functionn = 70m = 10x = 20y = 5a = 5b = 3solve(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 bfunction gcd($a, $b){ if ($a == 0) return $b; else return gcd($b % $a, $a);}// Function to calculate the// coordinates of the rectanglefunction 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> |
Output
12 0 27 9
Time complexity: O(log(min(a,b)))
Auxiliary space: O(log(min(a,b))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
