From 38a11596571d5281a9ba2c197d0e9cbebeb4039d Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Fri, 12 Dec 2025 12:27:51 +0100
Subject: aoc 2025, day 9, alternative solution for part 2 using geos (shapely)

---
 2025/src/day09-geos.cpp | 104 ++++++++++++++++++++++++++++++++++++++++++++++++
 makefile                |   3 ++
 2 files changed, 107 insertions(+)
 create mode 100644 2025/src/day09-geos.cpp

diff --git a/2025/src/day09-geos.cpp b/2025/src/day09-geos.cpp
new file mode 100644
index 0000000..c7d7df4
--- /dev/null
+++ b/2025/src/day09-geos.cpp
@@ -0,0 +1,104 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <tuple>
+#include <vector>
+
+// Geos
+#include <geos/geom/CoordinateSequence.h>
+#include <geos/geom/GeometryFactory.h>
+#include <geos/geom/Polygon.h>
+
+using namespace std;
+using namespace geos;
+using namespace geos::geom;
+
+namespace {
+
+using Pos = tuple<long, long>; // (x, y)
+
+vector<Pos>
+read_file(const filesystem::path& filename)
+{
+	ifstream file{ filename };
+
+	vector<Pos> data;
+
+	long x{};
+	long y{};
+	char skip{};
+
+	while ( file >> x >> skip >> y ) {
+		data.emplace_back(x, y);
+	}
+	return data;
+}
+
+std::unique_ptr<Polygon>
+makePolygon(const std::vector<Pos>& pts)
+{
+	CoordinateSequence coords;
+	for ( const auto [x, y]: pts ) {
+		coords.add(static_cast<double>(x), static_cast<double>(y));
+	}
+
+	// polygon schließen
+	coords.add(static_cast<double>(get<0>(pts[0])), static_cast<double>(get<1>(pts[0])));
+
+	const auto* factory = GeometryFactory::getDefaultInstance();
+
+	auto shell = factory->createLinearRing(coords);
+
+	return factory->createPolygon(std::move(shell), {});
+}
+
+void
+part2_geos(const vector<Pos>& data)
+{
+	auto poly = makePolygon(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);
+
+			auto rect = makePolygon(vector<Pos>{
+			    make_tuple(left, top),
+			    make_tuple(right, top),
+			    make_tuple(right, bottom),
+			    make_tuple(left, bottom),
+			    make_tuple(left, top),
+			});
+
+			if ( poly->covers(rect.get()) ) {
+				max_area = area;
+			}
+		}
+	}
+	cout << "Part 2: " << max_area << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+	auto data = read_file("data/day09.txt");
+	part2_geos(data);
+}
diff --git a/makefile b/makefile
index 536ac76..ed7a7b0 100644
--- a/makefile
+++ b/makefile
@@ -62,6 +62,9 @@ all: $(patsubst 2015/src/%.cpp,2015/bin/%,$(wildcard 2015/src/*.cpp)) \
 2025/bin/%: 2025/src/%.cpp | 2025/bin
 	c++ $(CPPFLAGS) $^ -o $@
 
+2025/bin/day09-geos: 2025/src/day09-geos.cpp | 2025/bin
+	c++ $(CPPFLAGS) -Wno-sign-conversion "-Wno-#warnings" $^ -lgeos -o $@
+
 2025/bin/day10p2: 2025/src/day10p2.cpp | 2025/bin
 	c++ $(CPPFLAGS) -Wno-sign-conversion $^ -lz3 -o $@
 
-- 
cgit v1.3