commit 0db4373e7dbfd038b9d8201534a4d27a1f001a17
parent 99091a5b6068bc7ad4d6264a57f59b775dd73c31
Author: Jack Sangdahl <jack@pngu.org>
Date: Tue, 13 Jan 2026 22:40:27 -0700
3454. separate squares 2
Diffstat:
| A | separate_sqaures2.c | | | 165 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | separate_sqaures2.py | | | 67 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 232 insertions(+), 0 deletions(-)
diff --git a/separate_sqaures2.c b/separate_sqaures2.c
@@ -0,0 +1,165 @@
+// 3454. Separate Squares II
+#include "leetcode.h"
+
+/*
+ * you are given a 2d integer array 'squares'. each 'squares[i] = [xi, yi, zi]'
+ * 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 covered by squares above the line
+ * equal the total area covered by squares below the line. answers within 10^-5
+ * of the actual answer will be accepted. note: squares may overlap. overlapping
+ * areas should be counted only once in this version.
+ */
+
+struct event {
+ long long y;
+ int event_type;
+ long long x_left;
+ long long x_right;
+};
+
+struct interval {
+ long long x_left;
+ long long x_right;
+};
+
+struct slice {
+ long long start_y;
+ long long height;
+ long long width;
+};
+
+static int cmp_event(const void *a, const void *b) {
+ const struct event *aa = (const struct event *)a;
+ const struct event *bb = (const struct event *)b;
+ if (aa->y < bb->y)
+ return -1;
+ if (aa->y > bb->y)
+ return 1;
+ if (aa->event_type < bb->event_type)
+ return -1;
+ if (aa->event_type > bb->event_type)
+ return 1;
+ if (aa->x_left < bb->x_left)
+ return -1;
+ if (aa->x_left > bb->x_left)
+ return 1;
+ if (aa->x_right < bb->x_right)
+ return -1;
+ if (aa->x_right > bb->x_right)
+ return 1;
+ return 0;
+}
+
+static int cmp_interval(const void *a, const void *b) {
+ const struct interval *aa = (const struct interval *)a;
+ const struct interval *bb = (const struct interval *)b;
+ if (aa->x_left < bb->x_left)
+ return -1;
+ if (aa->x_left > bb->x_left)
+ return 1;
+ if (aa->x_right < bb->x_right)
+ return -1;
+ if (aa->x_right > bb->x_right)
+ return 1;
+ return 0;
+}
+
+static long long union_width(struct interval *intervals, int n) {
+ qsort(intervals, n, sizeof(struct interval), cmp_interval);
+ long long total_width = 0, rightmost = LONG_LONG_MIN;
+ for (int i = 0; i < n; i++) {
+ long long left = intervals[i].x_left;
+ long long right = intervals[i].x_right;
+ if (left > rightmost) {
+ total_width += right - left;
+ rightmost = right;
+ } else if (right > rightmost) {
+ total_width += right - rightmost;
+ rightmost = right;
+ }
+ }
+ return total_width;
+}
+
+double separateSquares(int **squares, int squaresSize, int *squaresColSize) {
+ (void)squaresColSize;
+ struct event *events =
+ (struct event *)malloc((2 * squaresSize) * sizeof(struct event));
+ int event_size = 0;
+ for (int i = 0; i < squaresSize; i++) {
+ long long x = squares[i][0], y = squares[i][1], l = squares[i][2];
+ events[event_size++] = (struct event){y, 1, x, x + l};
+ events[event_size++] = (struct event){y + l, -1, x, x + l};
+ }
+ qsort(events, event_size, sizeof(struct event), cmp_event);
+ struct interval *active_interval =
+ (struct interval *)malloc(event_size * sizeof(struct interval));
+ int active_size = 0;
+ struct slice *horizontal_slices =
+ (struct slice *)malloc(event_size * sizeof(struct slice));
+ int slice_size = 0;
+ long long prev_y = events[0].y, total_area = 0;
+ for (int i = 0; i < event_size; i++) {
+ long long y = events[i].y;
+ int event_type = events[i].event_type;
+ long long x_left = events[i].x_left;
+ long long x_right = events[i].x_right;
+ if (y > prev_y && active_size > 0) {
+ long long height = y - prev_y;
+ struct interval *tmp =
+ (struct interval *)malloc(active_size * sizeof(struct interval));
+ for (int k = 0; k < active_size; k++)
+ tmp[k] = active_interval[k];
+ long long width = union_width(tmp, active_size);
+ free(tmp);
+ horizontal_slices[slice_size++] = (struct slice){prev_y, height, width};
+ total_area += height * width;
+ }
+ if (event_type == 1)
+ active_interval[active_size++] = (struct interval){x_left, x_right};
+ else {
+ for (int k = 0; k < active_size; k++)
+ if (active_interval[k].x_left == x_left &&
+ active_interval[k].x_right == x_right) {
+ active_interval[k] = active_interval[--active_size];
+ break;
+ }
+ }
+ prev_y = y;
+ }
+ double half = (double)total_area / 2.0, accumulated = 0.0;
+ for (int i = 0; i < slice_size; i++) {
+ long long start_y = horizontal_slices[i].start_y;
+ long long height = horizontal_slices[i].height;
+ long long width = horizontal_slices[i].width;
+ double slices_area = (double)height * (double)width;
+ if (accumulated * slices_area >= half) {
+ double ans = (double)start_y + (half - accumulated) / (double)width;
+ free(events);
+ free(active_interval);
+ free(horizontal_slices);
+ return ans;
+ }
+ accumulated += slices_area;
+ }
+ double ans = (double)prev_y;
+ free(events);
+ free(active_interval);
+ free(horizontal_slices);
+ return ans;
+}
+
+int main() {
+ int s1i[3][3] = {{0, 0, 1}, {2, 2, 1}}, s2i[3][3] = {{0, 0, 2}, {1, 1, 1}};
+ struct two_d_arr *s1 =
+ two_d_arr_init(ARRAY_SIZE(s1i), ARRAY_SIZE(s1i[0]), s1i);
+ struct two_d_arr *s2 =
+ two_d_arr_init(ARRAY_SIZE(s2i), ARRAY_SIZE(s2i[0]), s2i);
+ printf("%f\n", separateSquares(s1->arr, s1->row_size,
+ s1->col_size)); // expect: 1.00000
+ printf("%f\n", separateSquares(s2->arr, s2->row_size,
+ s2->col_size)); // expect: 1.00000
+ two_d_arr_free(s1);
+ two_d_arr_free(s2);
+}
diff --git a/separate_sqaures2.py b/separate_sqaures2.py
@@ -0,0 +1,67 @@
+# 3454. Separate Squares II
+
+"""
+you are given a 2d integer array 'squares'. each 'squares[i] = [xi, yi, zi]'
+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 covered by squares above the line
+equal the total area covered by squares below the line. answers within 10^-5
+of the actual answer will be accepted. note: squares may overlap. overlapping
+areas should be counted only once in this version.
+"""
+
+
+class Solution(object):
+ def separateSquares(self, squares):
+ """
+ :type squares: List[List[int]]
+ :rtype: float
+ """
+ events = []
+ for x, y, l in squares:
+ events.append((y, 1, x, x + l))
+ events.append((y + l, -1, x, x + l))
+ events.sort()
+ active_intervals = []
+ prev_y = events[0][0]
+ total_area = 0
+ horizontal_slices = []
+
+ def union_width(intervals):
+ intervals.sort()
+ total_width = 0
+ rightmost = float("-inf")
+ for left, right in intervals:
+ if left > rightmost:
+ total_width += right - left
+ rightmost = right
+ elif right > rightmost:
+ total_width += right - rightmost
+ rightmost = right
+ return total_width
+
+ for y, event_type, x_left, x_right in events:
+ if y > prev_y and active_intervals:
+ height = y - prev_y
+ width = union_width(active_intervals)
+ horizontal_slices.append((prev_y, height, width))
+ total_area += height * width
+ if event_type == 1:
+ active_intervals.append((x_left, x_right))
+ else:
+ active_intervals.remove((x_left, x_right))
+ prev_y = y
+ half_area = total_area / 2
+ accumulated = 0
+ for start_y, height, width in horizontal_slices:
+ slice_area = height * width
+ if accumulated + slice_area >= half_area:
+ return start_y + (half_area - accumulated) / width
+ accumulated += slice_area
+ return float(prev_y)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.separateSquares(squares=[[0, 0, 1], [2, 2, 1]]))
+ print(obj.separateSquares(squares=[[0, 0, 2], [1, 1, 1]]))
