← 返回 google 的题目列表Find a Horizontal Cut That Bisects Total Rectangle Area
类型：online_judge
You are given several axis-aligned rectangular cakes. Cake i is represented by (x_i, y_i, w_i, h_i), where (x_i, y_i) is its bottom-left corner, w_i is its width along the x-axis, and h_i is its height along the y-axis.
A horizontal line y = k cuts all cakes. For each cake, the area below the line is the portion of that rectangle in the half-plane y <= k; the area above is defined similarly. Areas of different cakes are summed independently. In particular, if rectangles overlap, the overlapped region is counted once for each cake.
Output a real number k such that the total area below the line equals half of the total cake area. If an interval of valid k values exists, output the smallest valid k.
Input Format
The first line contains an integer n, the number of cakes.
The next n lines each contain four integers x y w h.
Output Format
Print k with absolute or relative error at most 1e-5.
Constraints
1 <= n <= 2 * 10^5
0 <= x, y <= 10^9
1 <= w, h <= 10^9
Example 1
Input:
2
0 0 2 2
10 0 4 2
Output:
1.000000
Example 2
Input:
2
0 0 2 2
100 10 2 2
Output:
2.000000
The total area is 8. Every k in [2, 10] leaves area 4 below the line, so output the smallest valid value, 2.
Example
Input
2
0 0 2 2
10 0 4 2
Output
1.0000000000