Dada una hoja circular de radio R y la tarea es encontrar el número total de rectángulos con longitud y ancho integrales que se pueden cortar de la hoja circular, uno a la vez.
Ejemplos:
Entrada : R = 2
Salida : 8
Se pueden cortar 8 rectángulos de una hoja circular de radio 2.
Estos son: 1×1, 1×2, 2×1, 2×2, 1×3, 3×1, 2× 3, 3×2.
Entrada : R = 1
Salida : 1
Solo es posible un rectángulo con dimensiones 1 X 1.
Enfoque
Considere el siguiente diagrama,
Es fácil ver que ABCD es el rectángulo más grande que se puede formar en el círculo dado con radio R y centro O, que tiene dimensiones a X b
Deje caer una perpendicular AO tal que, ∠AOD = ∠AOB = 90°
Considere el siguiente diagrama para un análisis más detallado,
Consider triangles AOD and AOB, In these triangles, AO = AO (Common Side) ∠AOD = ∠AOB = 90° OD = OB = R Thus, by SAS congruence ▵AOD ≅ ▵AOB ∴ AD = AB by CPCT(i.e Corresponding Parts on Congruent Triangles) or, a = b => The rectangle ABCD is a square
El diámetro BD es la diagonal máxima que puede tener el rectángulo para poder ser cortado de la Hoja Circular.
Por lo tanto, todas las combinaciones de a y b pueden verificarse para formar todos los rectángulos posibles, y si la diagonal de cualquiera de esos rectángulos es menor o igual que la longitud de la diagonal del rectángulo más grande formado (es decir, 2 * R, donde R es el radio del círculo como se explicó anteriormente)
Ahora, la longitud máxima de a y b siempre será estrictamente menor que el diámetro del círculo, por lo que todos los valores posibles de a y b estarán en el intervalo cerrado [1, (2 * R-1)].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number of rectangles
// that can be cut from a circle of Radius R
#include <bits/stdc++.h>
using namespace std;
// Function to return the total possible
// rectangles that can be cut from the circle
int countRectangles(int radius)
{
int rectangles = 0;
// Diameter = 2 * Radius
int diameter = 2 * radius;
// Square of diameter which is the square
// of the maximum length diagonal
int diameterSquare = diameter * diameter;
// generate all combinations of a and b
// in the range (1, (2 * Radius - 1))(Both inclusive)
for (int a = 1; a < 2 * radius; a++) {
for (int b = 1; b < 2 * radius; b++) {
// Calculate the Diagonal length of
// this rectangle
int diagonalLengthSquare = (a * a + b * b);
// If this rectangle's Diagonal Length
// is less than the Diameter, it is a
// valid rectangle, thus increment counter
if (diagonalLengthSquare <= diameterSquare) {
rectangles++;
}
}
}
return rectangles;
}
// Driver Code
int main()
{
// Radius of the circle
int radius = 2;
int totalRectangles;
totalRectangles = countRectangles(radius);
cout << totalRectangles << " rectangles can be"
<< "cut from a circle of Radius " << radius;
return 0;
}
Java
// Java program to find the
// number of rectangles that
// can be cut from a circle
// of Radius R
import java.io.*;
class GFG
{
// Function to return
// the total possible
// rectangles that can
// be cut from the circle
static int countRectangles(int radius)
{
int rectangles = 0;
// Diameter = 2 * Radius
int diameter = 2 * radius;
// Square of diameter
// which is the square
// of the maximum length
// diagonal
int diameterSquare = diameter *
diameter;
// generate all combinations
// of a and b in the range
// (1, (2 * Radius - 1))
// (Both inclusive)
for (int a = 1;
a < 2 * radius; a++)
{
for (int b = 1;
b < 2 * radius; b++)
{
// Calculate the
// Diagonal length of
// this rectangle
int diagonalLengthSquare = (a * a +
b * b);
// If this rectangle's Diagonal
// Length is less than the Diameter,
// it is a valid rectangle, thus
// increment counter
if (diagonalLengthSquare <= diameterSquare)
{
rectangles++;
}
}
}
return rectangles;
}
// Driver Code
public static void main (String[] args)
{
// Radius of the circle
int radius = 2;
int totalRectangles;
totalRectangles = countRectangles(radius);
System.out.println(totalRectangles +
" rectangles can be " +
"cut from a circle of" +
" Radius " + radius);
}
}
// This code is contributed
// by anuj_67.
Python3
# Python3 program to find # the number of rectangles # that can be cut from a # circle of Radius R Function # to return the total possible # rectangles that can be cut # from the circle def countRectangles(radius): rectangles = 0 # Diameter = 2 * Radius diameter = 2 * radius # Square of diameter which # is the square of the # maximum length diagonal diameterSquare = diameter * diameter # generate all combinations # of a and b in the range # (1, (2 * Radius - 1))(Both inclusive) for a in range(1, 2 * radius): for b in range(1, 2 * radius): # Calculate the Diagonal # length of this rectangle diagonalLengthSquare = (a * a + b * b) # If this rectangle's Diagonal # Length is less than the # Diameter, it is a valid # rectangle, thus increment counter if (diagonalLengthSquare <= diameterSquare) : rectangles += 1 return rectangles # Driver Code # Radius of the circle radius = 2 totalRectangles = countRectangles(radius) print(totalRectangles , "rectangles can be" , "cut from a circle of Radius" , radius) # This code is contributed by Smita
C#
// C# program to find the
// number of rectangles that
// can be cut from a circle
// of Radius R
using System;
class GFG
{
// Function to return
// the total possible
// rectangles that can
// be cut from the circle
static int countRectangles(int radius)
{
int rectangles = 0;
// Diameter = 2 * Radius
int diameter = 2 * radius;
// Square of diameter
// which is the square
// of the maximum length
// diagonal
int diameterSquare = diameter *
diameter;
// generate all combinations
// of a and b in the range
// (1, (2 * Radius - 1))
// (Both inclusive)
for (int a = 1;
a < 2 * radius; a++)
{
for (int b = 1;
b < 2 * radius; b++)
{
// Calculate the
// Diagonal length of
// this rectangle
int diagonalLengthSquare = (a * a +
b * b);
// If this rectangle's
// Diagonal Length is
// less than the Diameter,
// it is a valid rectangle,
// thus increment counter
if (diagonalLengthSquare <=
diameterSquare)
{
rectangles++;
}
}
}
return rectangles;
}
// Driver Code
public static void Main ()
{
// Radius of the circle
int radius = 2;
int totalRectangles;
totalRectangles = countRectangles(radius);
Console.WriteLine(totalRectangles +
" rectangles can be " +
"cut from a circle of" +
" Radius " + radius);
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP program to find the
// number of rectangles that
// can be cut from a circle
// of Radius R
// Function to return the
// total possible rectangles
// that can be cut from the circle
function countRectangles($radius)
{
$rectangles = 0;
// Diameter = 2 * $Radius
$diameter = 2 * $radius;
// Square of diameter which
// is the square of the
// maximum length diagonal
$diameterSquare = $diameter *
$diameter;
// generate all combinations
// of a and b in the range
// (1, (2 * Radius - 1))(Both inclusive)
for ($a = 1;
$a < 2 * $radius; $a++)
{
for ($b = 1;
$b < 2 * $radius; $b++)
{
// Calculate the Diagonal
// length of this rectangle
$diagonalLengthSquare = ($a * $a +
$b * $b);
// If this rectangle's Diagonal
// Length is less than the
// Diameter, it is a valid
// rectangle, thus increment counter
if ($diagonalLengthSquare <= $diameterSquare)
{
$rectangles++;
}
}
}
return $rectangles;
}
// Driver Code
// Radius of the circle
$radius = 2;
$totalRectangles;
$totalRectangles = countRectangles($radius);
echo $totalRectangles , " rectangles can be " ,
"cut from a circle of Radius " , $radius;
// This code is contributed
// by anuj_67.
?>
Javascript
<script>
// java script program to find the
// number of rectangles that
// can be cut from a circle
// of Radius R
// Function to return the
// total possible rectangles
// that can be cut from the circle
function countRectangles(radius)
{
let rectangles = 0;
// Diameter = 2 * $Radius
let diameter = 2 * radius;
// Square of diameter which
// is the square of the
// maximum length diagonal
let diameterSquare = diameter *
diameter;
// generate all combinations
// of a and b in the range
// (1, (2 * Radius - 1))(Both inclusive)
for (let a = 1;a < 2 * radius; a++)
{
for (let b = 1;
b < 2 * radius; b++)
{
// Calculate the Diagonal
// length of this rectangle
let diagonalLengthSquare = (a * a +
b * b);
// If this rectangle's Diagonal
// Length is less than the
// Diameter, it is a valid
// rectangle, thus increment counter
if (diagonalLengthSquare <= diameterSquare)
{
rectangles++;
}
}
}
return rectangles;
}
// Driver Code
// Radius of the circle
let radius = 2;
let totalRectangles;
totalRectangles = countRectangles(radius);
document.write( totalRectangles + " rectangles can be cut from a circle of Radius " +radius);
// This code is contributed by sravan kumar
</script>
Producción:
8 rectangles can be cut from a circle of Radius 2
Complejidad del Tiempo: O(R 2 ), donde R es el Radio del Círculo
Complejidad espacial : O (1) ya que usa variables constantes