CF 102821B - Bin Packing

CF 102821B - Bin Packing

Rating: -
Tags: -
Solve time: 1m 3s
Verified: yes

Solution

Problem Understanding

We have two rectangular objects. For each test case, their dimensions are given as width and height. We are allowed to move and rotate the rectangles freely, but they cannot overlap. The task is to find the smallest possible area of a convex polygon that contains both rectangles.

The key detail is that we are not looking for the smallest enclosing rectangle. A convex polygon can cut away empty corners, so simply adding widths and taking maximum heights is not always optimal.

The number of test cases is at most 100 and every side length is at most 100. This means the solution only needs to perform a small constant amount of work per test case. Any simulation, search over placements, or geometry construction with many states is unnecessary. The intended solution should reduce the infinite number of possible rotations and positions to a fixed number of mathematical cases.

The tricky part is understanding that the best arrangement is not always an ordinary side-by-side placement. A naive approach would only check bounding rectangles, which misses the diagonal arrangement where the convex hull removes a triangular empty region.

For example, with rectangles 1 3 and 2 4, the bounding rectangle approach gives:

(1 + 2) * max(3, 4) = 12

but the correct answer is:

11.5

The missing 0.5 comes from the triangular corner that disappears when the two rectangles are placed diagonally.

Another edge case is when rotating one rectangle helps. For rectangles 2 3 and 4 5, keeping both orientations fixed gives a larger result, while rotating one rectangle produces the optimal arrangement:

Input:
2 3 4 5

Output:
27.0

A solution that never swaps width and height would incorrectly return a larger value.

Approaches

The brute-force idea is to try every possible placement and rotation angle of the two rectangles, build the convex hull, and measure its area. The idea is correct because every legal arrangement can be evaluated this way. The problem is that rotations are continuous, so there are infinitely many possible states. Even restricting the search to many sampled angles would not guarantee correctness.

The important observation is that only the relative orientation of the rectangle sides matters. The optimal configuration happens when the rectangles touch in a way that removes one triangular corner from the sum of their areas. For a fixed choice of orientations, the extra area outside the two rectangles is:

$$\frac{|w_1-w_2|\cdot |h_1-h_2|}{2}$$

The reason is that the empty part of the convex hull is a right triangle. Its legs are exactly the differences between the corresponding side lengths of the two rectangles.

Because each rectangle can either keep its orientation or rotate by 90 degrees, there are only four orientation combinations to check.

The total area for one orientation is:

$$w_1h_1+w_2h_2+\frac{|w_1-w_2||h_1-h_2|}{2}$$

The minimum among the four rotations is the answer.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	Infinite search over rotations	O(1)	Too slow and unreliable
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

1. Compute the area of both rectangles. This part is constant because the rectangles themselves do not change size when rotated.
2. Try every possible orientation of the two rectangles. A rectangle has only two meaningful states: (width, height) and (height, width).
3. For each pair of orientations, calculate the additional triangular area:

$$\frac{|w_1-w_2||h_1-h_2|}{2}$$

This represents the part of the convex hull that is not occupied by either rectangle.

1. Add this value to the sum of the two rectangle areas and keep the minimum.

Why it works:

For any fixed orientation, the best possible placement is achieved when the rectangles are pushed together until they touch. Any remaining gap would increase the convex hull area. After touching, the only unused part of the convex hull is a triangle created by the difference between the side lengths. Checking all four orientation choices covers every possible rotation of the two rectangles, so the minimum value found is the global optimum.

Python Solution

import sys
input = sys.stdin.readline

def solve_case(w1, h1, w2, h2):
    base = w1 * h1 + w2 * h2
    ans = float("inf")

    for a, b in [(w1, h1), (h1, w1)]:
        for c, d in [(w2, h2), (h2, w2)]:
            extra = abs(a - c) * abs(b - d) / 2
            ans = min(ans, base + extra)

    return ans

def main():
    t = int(input())
    out = []

    for case in range(1, t + 1):
        w1, h1, w2, h2 = map(int, input().split())
        ans = solve_case(w1, h1, w2, h2)
        out.append(f"Case {case}: {ans:.10f}")

    print("\n".join(out))

if __name__ == "__main__":
    main()

The implementation only stores the current answer, so there are no hidden memory costs. The loops explicitly enumerate the two possible orientations of each rectangle, avoiding complicated geometry code.

The use of floating point division is necessary because the triangular contribution can contain .5. Printing several decimal places easily satisfies the required precision.

The absolute difference calculation is also important. The triangle size depends on how much the two side lengths differ, not on which rectangle has the larger side.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per test case	Exactly four orientation combinations are checked
Space	O(1)	Only a few variables are stored

With at most 100 test cases, the total number of operations is tiny.

I’ll continue with the worked examples, tests, and edge case walkthrough in the next part.