HTMLify
separate-squares-ii.py
Views: 3 | Author: prakhardoneria
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | from typing import List class Solution: def separateSquares(self, squares: List[List[int]]) -> float: x_coords = set() for x, y, l in squares: x_coords.add(x) x_coords.add(x + l) sorted_x = sorted(list(x_coords)) x_map = {x: i for i, x in enumerate(sorted_x)} n_x = len(sorted_x) count = [0] * (4 * n_x) covered_len = [0.0] * (4 * n_x) def update(v, tl, tr, l, r, add): if l > r: return if l == tl and r == tr: count[v] += add else: tm = (tl + tr) // 2 update(2*v, tl, tm, l, min(r, tm), add) update(2*v+1, tm+1, tr, max(l, tm+1), r, add) if count[v] > 0: covered_len[v] = sorted_x[tr+1] - sorted_x[tl] else: if tl != tr: covered_len[v] = covered_len[2*v] + covered_len[2*v+1] else: covered_len[v] = 0 events = [] for x, y, l in squares: events.append((y, 1, x, x + l)) events.append((y + l, -1, x, x + l)) events.sort() y_intervals = [] prev_y = events[0][0] for y, typ, x1, x2 in events: if y > prev_y: y_intervals.append((prev_y, y, covered_len[1])) update(1, 0, n_x - 2, x_map[x1], x_map[x2] - 1, typ) prev_y = y total_area = sum((y2 - y1) * w for y1, y2, w in y_intervals if w > 0) target = total_area / 2.0 current_cumulative_area = 0.0 for y1, y2, w in y_intervals: if w == 0: continue segment_area = w * (y2 - y1) if current_cumulative_area + segment_area >= target - 1e-9: # The line is within this y-interval needed_area = target - current_cumulative_area return y1 + (needed_area / w) current_cumulative_area += segment_area return float(events[-1][0]) |