Welcome to Subscribe On Youtube

3453. Separate Squares I

Description

You are given a 2D integer array squares. Each squares[i] = [xi, yi, li] represents the coordinates of the bottom-left point and the side length of a square parallel to the x-axis.

Find the minimum y-coordinate value of a horizontal line such that the total area of the squares above the line equals the total area of the squares below the line.

Answers within 10-5 of the actual answer will be accepted.

Note: Squares may overlap. Overlapping areas should be counted multiple times.

 

Example 1:

Input: squares = [[0,0,1],[2,2,1]]

Output: 1.00000

Explanation:

Any horizontal line between y = 1 and y = 2 will have 1 square unit above it and 1 square unit below it. The lowest option is 1.

Example 2:

Input: squares = [[0,0,2],[1,1,1]]

Output: 1.16667

Explanation:

The areas are:

  • Below the line: 7/6 * 2 (Red) + 1/6 (Blue) = 15/6 = 2.5.
  • Above the line: 5/6 * 2 (Red) + 5/6 (Blue) = 15/6 = 2.5.

Since the areas above and below the line are equal, the output is 7/6 = 1.16667.

 

Constraints:

  • 1 <= squares.length <= 5 * 104
  • squares[i] = [xi, yi, li]
  • squares[i].length == 3
  • 0 <= xi, yi <= 109
  • 1 <= li <= 109
  • The total area of all the squares will not exceed 1012.

Solutions

Solution 1

  • class Solution {
    private int[][] squares;
    private double s;

    private boolean check(double y1) {
        double t = 0.0;
        for (int[] a : squares) {
            int y = a[1];
            int l = a[2];
            if (y < y1) {
                t += (double) l * Math.min(y1 - y, l);
            }
        }
        return t >= s / 2.0;
    }

    public double separateSquares(int[][] squares) {
        this.squares = squares;
        s = 0.0;
        double l = 0.0;
        double r = 0.0;
        for (int[] a : squares) {
            s += (double) a[2] * a[2];
            r = Math.max(r, a[1] + a[2]);
        }

        double eps = 1e-5;
        while (r - l > eps) {
            double mid = (l + r) / 2.0;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
}


  • class Solution {
public:
    vector<vector<int>>* squares;
    double s;

    bool check(double y1) {
        double t = 0.0;
        for (const auto& a : *squares) {
            int y = a[1];
            int l = a[2];
            if (y < y1) {
                t += (double) l * min(y1 - y, (double) l);
            }
        }
        return t >= s / 2.0;
    }

    double separateSquares(vector<vector<int>>& squares) {
        this->squares = &squares;
        s = 0.0;
        double l = 0.0;
        double r = 0.0;
        for (const auto& a : squares) {
            s += (double) a[2] * a[2];
            r = max(r, (double) a[1] + a[2]);
        }
        const double eps = 1e-5;
        while (r - l > eps) {
            double mid = (l + r) / 2.0;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
};


  • class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        def check(y1: float) -> bool:
            t = 0
            for _, y, l in squares:
                if y < y1:
                    t += l * min(y1 - y, l)
            return t >= s / 2

        s = sum(a[2] * a[2] for a in squares)
        l, r = 0, max(a[1] + a[2] for a in squares)
        eps = 1e-5
        while r - l > eps:
            mid = (l + r) / 2
            if check(mid):
                r = mid
            else:
                l = mid
        return r


  • func separateSquares(squares [][]int) float64 {
	s := 0.0
	check := func(y1 float64) bool {
		t := 0.0
		for _, a := range squares {
			y := a[1]
			l := a[2]
			if float64(y) < y1 {
				h := min(float64(l), y1-float64(y))
				t += float64(l) * h
			}
		}
		return t >= s/2.0
	}
	l, r := 0.0, 0.0
	for _, a := range squares {
		s += float64(a[2] * a[2])
		r = max(r, float64(a[1]+a[2]))
	}

	const eps = 1e-5
	for r-l > eps {
		mid := (l + r) / 2.0
		if check(mid) {
			r = mid
		} else {
			l = mid
		}
	}
	return r
}


  • function separateSquares(squares: number[][]): number {
    const check = (y1: number): boolean => {
        let t = 0;
        for (const [_, y, l] of squares) {
            if (y < y1) {
                t += l * Math.min(y1 - y, l);
            }
        }
        return t >= s / 2;
    };

    let s = 0;
    let l = 0;
    let r = 0;
    for (const a of squares) {
        s += a[2] * a[2];
        r = Math.max(r, a[1] + a[2]);
    }

    const eps = 1e-5;
    while (r - l > eps) {
        const mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


  • impl Solution {
    pub fn separate_squares(squares: Vec<Vec<i32>>) -> f64 {
        let mut s: f64 = 0.0;

        let mut l: f64 = 0.0;
        let mut r: f64 = 0.0;

        for a in squares.iter() {
            let len = a[2] as f64;
            s += len * len;
            r = r.max((a[1] + a[2]) as f64);
        }

        let check = |y1: f64| -> bool {
            let mut t: f64 = 0.0;
            for a in squares.iter() {
                let y = a[1] as f64;
                let l = a[2] as f64;
                if y < y1 {
                    let h = l.min(y1 - y);
                    t += l * h;
                }
            }
            t >= s / 2.0
        };

        const EPS: f64 = 1e-5;
        while r - l > EPS {
            let mid = (l + r) / 2.0;
            if check(mid) {
                r = mid;
            } else {
                l = mid;
            }
        }
        r
    }
}

All Problems

All Solutions