From d88a2248710f3b9a9a2a6e16707f20b5662d72ab Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Tue, 9 Dec 2025 21:18:20 +0100
Subject: aoc 2025, day 9, part 2

---
 2025/src/day09.cpp | 88 +++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 87 insertions(+), 1 deletion(-)

(limited to '2025/src')

diff --git a/2025/src/day09.cpp b/2025/src/day09.cpp
index f46112a..796bf07 100644
--- a/2025/src/day09.cpp
+++ b/2025/src/day09.cpp
@@ -8,7 +8,8 @@ using namespace std;
 
 namespace {
 
-using Pos = tuple<long, long>;
+using Pos     = tuple<long, long>; // (x, y)
+using Segment = tuple<Pos, Pos>;   // (p1, p2)
 
 vector<Pos>
 read_file(const filesystem::path& filename)
@@ -46,6 +47,90 @@ part1(const vector<Pos>& data)
 	cout << "Part 1: " << area << '\n';
 }
 
+vector<Segment>
+build_edges(const vector<Pos>& data)
+{
+	vector<Segment> edges;
+	for ( size_t i = 0; i != data.size(); ++i ) {
+		edges.emplace_back(data[i], data[(i + 1) % data.size()]);
+	}
+	return edges;
+}
+
+bool
+intersects(const Segment& line, const tuple<long, long, long, long>& rect)
+{
+	const auto [start, end] = line;
+	const auto [x1, y1]     = start;
+	const auto [x2, y2]     = end;
+
+	const auto [left, top, right, bottom] = rect;
+
+	if ( x1 == x2 ) {
+		if ( x1 <= left || x1 >= right ) {
+			return false;
+		}
+
+		const auto min_y = min(y1, y2);
+		const auto max_y = max(y1, y2);
+
+		return max_y > top && min_y < bottom;
+	}
+
+	if ( y1 == y2 ) {
+		if ( y1 <= top || y1 >= bottom ) {
+			return false;
+		}
+
+		auto min_x = min(x1, x2);
+		auto max_x = max(x1, x2);
+
+		return max_x > left && min_x < right;
+	}
+
+	return false;
+}
+
+bool
+contains(const vector<Segment>& poly, const tuple<long, long, long, long>& rect)
+{
+	return ranges::all_of(poly, [&](const auto& line) { return !intersects(line, rect); });
+}
+
+void
+part2(const vector<Pos>& data)
+{
+	const auto poly = build_edges(data);
+
+	auto max_area = numeric_limits<long>::min();
+
+	for ( size_t i = 0; i != data.size(); ++i ) {
+		for ( size_t j = i + 1; j != data.size(); ++j ) {
+			const auto [x1, y1] = data[i];
+			const auto [x2, y2] = data[j];
+
+			const auto width  = abs(x1 - x2) + 1;
+			const auto height = abs(y1 - y2) + 1;
+
+			const auto area = width * height;
+
+			if ( area <= max_area ) {
+				continue;
+			}
+
+			const auto left   = min(x1, x2);
+			const auto right  = max(x1, x2);
+			const auto top    = min(y1, y2);
+			const auto bottom = max(y1, y2);
+
+			if ( contains(poly, { left, top, right, bottom }) ) {
+				max_area = area;
+			}
+		}
+	}
+	cout << "Part 2: " << max_area << '\n';
+}
+
 } // namespace
 
 int
@@ -53,4 +138,5 @@ main()
 {
 	auto data = read_file("data/day09.txt");
 	part1(data);
+	part2(data);
 }
-- 
cgit v1.3