# Packing Rectangles (Contest)

Problem Statement :&#x20;

There are n rectangles of the same size: w in width and h in length. It is required to find a square of the smallest size into which these rectangles can be packed. Rectangles cannot be rotated.InputThe first line of the input contains three space-separated integers w, h and n.\
\
Constraints\
1 ≤ w, h, n ≤ 109OutputOutput the minimum length of a side of a square, into which the given rectangles can be packed.ExampleSample Input :\
2 3 10\
Sample Output:\
9\
\
Explanation:\
9 is the minimum size of the square in which all these rectangles can fit.\
![](https://d3dyfaf3iutrxo.cloudfront.net/general/upload/7aef090772524a368cf0cbe754a484a9.png)

link:<https://my.newtonschool.co/playground/code/vkeb3vtr6bb4>

````java
```java
import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework

// don't change the name of this class
// you can add inner classes if needed
class Main {
    public static void main (String[] args) {
        // Your code here
        Scanner sc = new Scanner(System.in);
        long w = sc.nextLong();
        long h = sc.nextLong();
        long n = sc.nextLong();

        long left = 1, right = (long)(1e18)*1L;
        long ans = -1;
        while(left <= right)
        {
            long mid = left + (right - left)/2;
            long sq = mid;
            long x = sq/w;
            long y = sq/h;
            if(((y>0 && x >= ((n-1) / y + 1)) || (x > 0 && y >= ((n - 1) / x + 1)))) {
                ans = sq;
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        } 
        System.out.print(ans);
    }
}

///method 02
```java
import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework
import java.math.BigInteger;

// don't change the name of this class
// you can add inner classes if needed
class Main {
    public static void main (String[] args) {
        // Your code here
        Scanner sc = new Scanner(System.in);
        long w = sc.nextLong();
        long h = sc.nextLong();
        int n = sc.nextInt();
        long s =0L,e = 1000000000000000L;
        long ans =e;
        while(s<=e){
            long m = (s+e)/2;
            long rowFit = m/w;
            long colFit = m/h;
            BigInteger maxFit = new BigInteger(String.valueOf(rowFit)).multiply(new BigInteger(String.valueOf(colFit)));
            if(maxFit.compareTo(BigInteger.valueOf(n))>=0){
                ans=m;
                e=m-1;
            }
            else{
                s=m+1;
            }
        }
        System.out.println(ans);
    }
}
```
````
