Encuentre la pieza más grande para cortar de Pizza de manera que cada una obtenga al menos una pieza con la misma área

Dada una array arr[] que denota el radio de las pizzas circulares y un número entero N que denota el número de amigos. La tarea es calcular el trozo más grande que se puede cortar de las pizzas para que cada amigo obtenga un trozo de pizza con la misma área.
No está permitido hacer un trozo de más de una pizza y cada amigo recibe solo un trozo de pizza. 

Ejemplo:

Entrada: arr[] = {1, 1, 1, 2, 2, 3}, N = 6.
Salida: 7,0686
Explicación: Tome el área de la pizza con un radio de 3 y divídala por 4. (Área 28,743 / 4 = 7,0686). Use una pieza de tamaño similar de la pizza restante de radio 2 porque el área total de la pizza con radio 2 es> 7.0686

Entrada: arr[] = {6, 7}, N = 12
Salida: 21,9911

Enfoque: este problema se puede resolver utilizando la búsqueda binaria . Siga los pasos a continuación para resolver el problema dado.

• Ordene la array, esto ayudará a usar la búsqueda binaria en ella.
• Ahora, el área máxima que puede tener la persona es maxArea=π* a[n-1]*a[n-1] ( área de un círculo – π*r ² ).
• Sea el área mínima que puede tener la persona minArea=0.
• Ahora aplique la búsqueda binaria en este rango dado.
• Como π es constante, aplique la búsqueda binaria desde  minArea=0 hasta maxArea= a[n-1]*a[n-1] y luego, después de obtener (radio requerido * radio requerido) a través de esta búsqueda binaria, multiplique π en ella.
• Como la mitad de la búsqueda binaria también puede estar en decimal, para eso ejecute una búsqueda binaria para una cierta cantidad de iteraciones, digamos 500 .
• Necesitamos implementar una posible función también para la mitad dada de la búsqueda binaria.
• Si esa mitad es válida para el problema, eso significa que se calcula la respuesta requerida y se requiere ir a la derecha de la búsqueda binaria para obtener la respuesta más grande posible.
• Si esa mitad no es válida para el problema, eso significa que todas las respuestas a la derecha de esa mitad tampoco serán válidas, así que vaya a la izquierda.
• Ahora, en la función isPossible() , para todos y cada uno de los radios, verifique cuántas personas pueden obtener pedazos de esa pizza, si el total de personas que obtienen pizza> = amigos dados, eso significa que es válido, así que vaya a la derecha en la búsqueda binaria, de lo contrario, a la izquierda.
• Imprime la respuesta encontrada al hacer las operaciones anteriores.

A continuación se muestra la implementación del enfoque anterior:

#include <bits/stdc++.h>
using namespace std;
 
// Function to check if current distribution
// is valid or not
bool isPossible(double x, int a[], int n, int k)
{
    for (int i = n - 1; i >= 0; i--) {
        int p = (a[i] * a[i]) / x;
        k -= p;
 
        if (k <= 0)
            return true;
    }
 
    if (k <= 0)
        return true;
    return false;
}
 
// Function to solve given problem
long double maximumAreaPizza(int a[], int n, int k)
{
    sort(a, a + n);
 
    double l = 0, r = a[n - 1] * a[n - 1];
 
    int count = 500;
    double res = 0;
    while (count--) {
        double mid = double(l + r) / 2.0000;
        if (isPossible(mid, a, n, k)) {
            // cout << mid << " ";
            res = mid;
            l = mid;
        }
        else
            r = mid;
    }
 
    // After calculating radius*radius for
    // area multiply by pi(3.14) to get area
    long double p1 = res * 3.14159265359;
    return p1;
}
 
// Driver Code
int main()
{
 
    // Number of pizza
    int N = 6;
 
    // Radius of all pizzas
    int arr[] = { 1, 1, 1, 2, 2, 3 };
 
    // Number of friends
    int K = 6;
 
    // Function Call
    cout << maximumAreaPizza(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
 class GFG {
 
// Function to check if current distribution
// is valid or not
static boolean isPossible(double x, int []a, int n, int k)
{
    for (int i = n - 1; i >= 0; i--) {
        int p = (int)((a[i] * a[i]) / x);
        k -= p;
 
        if (k <= 0)
            return true;
    }
 
    if (k <= 0)
        return true;
    return false;
}
 
// Function to solve given problem
static double maximumAreaPizza(int []a, int n, int k)
{
    Arrays.sort(a);
 
    double l = 0, r = a[n - 1] * a[n - 1];
 
    int count = 500;
    double res = 0;
    while (count > 0) {
        double mid = (double)(l + r) / 2.0000;
        if (isPossible(mid, a, n, k)) {
            // cout << mid << " ";
            res = mid;
            l = mid;
        }
        else
            r = mid;
        count--;
    }
 
    // After calculating radius*radius for
    // area multiply by pi(3.14) to get area
    double p1 = res * 3.14159265359;
    return p1;
}
 
  // Driver Code
  public static void main(String args[])
  {
    // Number of pizza
    int N = 6;
 
    // Radius of all pizzas
    int []arr = { 1, 1, 1, 2, 2, 3 };
 
    // Number of friends
    int K = 6;
 
    // Function Call
    System.out.println(maximumAreaPizza(arr, N, K));
 
  }
}
 
// This code is contributed by code_hunt.

import math
 
# Function to solve the given problem
def maximumAreaPizza(radii, numberOfGuests):
    areas = [math.pi * r * r for r in radii]
    def isPossible(x):
        k = 0
        for a in areas:
            k += a // x
            if k >= numberOfGuests:
                return True
        return False
     
    l, r = 0, max(areas)
    while l + 1e-5 <= r:
        x = (l + r) / 2
        if isPossible(x):
            l = x
        else:
            r = x
    return round(x, 4)
 
# Driver Code
arr = [ 1, 1, 1, 2, 2, 3] 
N = 6
print(maximumAreaPizza(arr, N))

using System;
class GFG
{
   
// Function to check if current distribution
// is valid or not
static bool isPossible(double x, int []a, int n, int k)
{
    for (int i = n - 1; i >= 0; i--) {
        int p = (int)((a[i] * a[i]) / x);
        k -= p;
 
        if (k <= 0)
            return true;
    }
 
    if (k <= 0)
        return true;
    return false;
}
 
// Function to solve given problem
static double maximumAreaPizza(int []a, int n, int k)
{
    Array.Sort(a);
 
    double l = 0, r = a[n - 1] * a[n - 1];
 
    int count = 500;
    double res = 0;
    while (count > 0) {
        double mid = (double)(l + r) / 2.0000;
        if (isPossible(mid, a, n, k)) {
            // cout << mid << " ";
            res = mid;
            l = mid;
        }
        else
            r = mid;
        count--;
    }
 
    // After calculating radius*radius for
    // area multiply by pi(3.14) to get area
    double p1 = res * 3.14159265359;
    return p1;
}
 
// Driver Code
public static void Main()
{
 
    // Number of pizza
    int N = 6;
 
    // Radius of all pizzas
    int []arr = { 1, 1, 1, 2, 2, 3 };
 
    // Number of friends
    int K = 6;
 
    // Function Call
    Console.Write(maximumAreaPizza(arr, N, K));
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to check if current distribution
       // is valid or not
       function isPossible(x, a, n, k) {
           for (let i = n - 1; i >= 0; i--) {
               let p = Math.floor((a[i] * a[i]) / x);
               k -= p;
 
               if (k <= 0)
                   return true;
           }
 
           if (k <= 0)
               return true;
           return false;
       }
 
       // Function to solve given problem
       function maximumAreaPizza(a, n, k) {
           a.sort(function (a, b) { return a - b })
 
           let l = 0, r = a[n - 1] * a[n - 1];
 
           let count = 500;
           let res = 0;
           while (count--) {
               let mid = (l + r) / 2.0000;
               if (isPossible(mid, a, n, k)) {
 
                   res = mid;
                   l = mid;
               }
               else
                   r = mid;
           }
 
           // After calculating radius*radius for
           // area multiply by pi(3.14) to get area
           let p1 = res * 3.14159265359;
           return p1;
       }
 
       // Driver Code
 
       // Number of pizza
       let N = 6;
 
       // Radius of all pizzas
       let arr = [1, 1, 1, 2, 2, 3];
 
       // Number of friends
       let K = 6;
 
       // Function Call
       document.write(maximumAreaPizza(arr, N, K).toPrecision(6));
        
      // This code is contributed by Potta Lokesh
   </script>

7.06858

Complejidad temporal: O(N logN) 
Espacio auxiliar: O(1)