import java.util.*;

class RectangleSplitter {

static class Event {

int x, y1, y2;

boolean isStart;

Event(int x, int y1, int y2, boolean isStart) {

this.x = x;

this.y1 = y1;

this.y2 = y2;

this.isStart = isStart;

}

}

public static int findSplittingLine(int[][] rectangles) {

List<Event> events = new ArrayList<>();

for (int[] rect : rectangles) {

events.add(new Event(rect[0], rect[1], rect[3], true)); // Left edge

events.add(new Event(rect[2], rect[1], rect[3], false)); // Right edge

}

// Sort events by x, ensuring starts appear before ends at same x

events.sort((a, b) -> a.x - b.x);

int totalArea = computeTotalArea(events);

int halfArea = totalArea / 2;

int accumulatedArea = 0;

TreeMap<Integer, Integer> activeRectangles = new TreeMap<>();

for (Event event : events) {

int prevX = event.x;

int prevHeight = computeActiveHeight(activeRectangles);

accumulatedArea += prevHeight * (event.x - prevX);

if (accumulatedArea >= halfArea) {

return event.x;

}

updateActiveRectangles(activeRectangles, event);

}

return -1; // No valid split found

}

private static int computeTotalArea(List<Event> events) {

TreeMap<Integer, Integer> activeRectangles = new TreeMap<>();

int lastX = events.get(0).x, totalArea = 0;

for (Event event : events) {

int height = computeActiveHeight(activeRectangles);

totalArea += height * (event.x - lastX);

lastX = event.x;

updateActiveRectangles(activeRectangles, event);

}

return totalArea;

}

private static int computeActiveHeight(TreeMap<Integer, Integer> activeRectangles) {

int height = 0, prevY = -1;

for (var entry : activeRectangles.entrySet()) {

if (prevY != -1) height += entry.getKey() - prevY;

prevY = entry.getKey();

}

return height;

}

private static void updateActiveRectangles(TreeMap<Integer, Integer> activeRectangles, Event event) {

if (event.isStart) {

activeRectangles.put(event.y1, activeRectangles.getOrDefault(event.y1, 0) + 1);

activeRectangles.put(event.y2, activeRectangles.getOrDefault(event.y2, 0) - 1);

} else {

if (activeRectangles.get(event.y1) == 1) activeRectangles.remove(event.y1);

else activeRectangles.put(event.y1, activeRectangles.get(event.y1) - 1);

if (activeRectangles.get(event.y2) == -1) activeRectangles.remove(event.y2);

else activeRectangles.put(event.y2, activeRectangles.get(event.y2) + 1);

}

}

public static void main(String[] args) {

int[][] rectangles = {

{1, 1, 4, 4}, // x_left, y_bottom, x_right, y_top

{2, 2, 5, 5},

{3, 1, 6, 3}

};

int splitX = findSplittingLine(rectangles);

System.out.println("Splitting vertical line at x = " + splitX);

}

}