Solution to "Infi - Advent of Code 2023" on https://aoc.infi.nl/

solve.cpp

/*
 * solve.cpp -- Solution to "Infi - Advent of Code 2023" on https://aoc.infi.nl/
 *
 * $ curl https://aoc.infi.nl/api/aoc/input/2023/H9RCB9D9PD6C >input
 * $ g++ -std=c++17 solve.cc -o solve
 * $ ./solve <input
 *
 */
#include <algorithm>
#include <cassert>
#include <cmath>
#include <initializer_list>
#include <iostream>
#include <regex>
#include <string>
#include <tuple>
#include <vector>

static auto midpoint(double ax, double ay, double bx, double by) {
	return std::make_tuple((ax + bx) / 2, (ay + by) / 2);
}

static auto circumcircle(double bx, double by, double cx, double cy) {
	auto d = 2 * (bx * cy - by * cx);
	auto br2 = bx * bx + by * by;
	auto cr2 = cx * cx + cy * cy;
	auto ux = (cy * br2 - by * cr2) / d;
	auto uy = (bx * cr2 - cx * br2) / d;
	auto r = std::hypot(ux, uy);
	return std::make_tuple(ux, uy, r);
}

static auto circumcircle(double ax, double ay, double bx, double by, double cx, double cy) {
	auto [ux1, uy1, r] = circumcircle(bx - ax, by - ay, cx - ax, cy - ay);
	return std::make_tuple(ux1 + ax, uy1 + ay, r);
}

/**
 * Is it true that all the given `(x, y)` points fit in a circle with
 * center `(ox, oy)` and radius `r`? Skip points with index in the
 * list `taboo`, as those points are known to lie exactly on the
 * circle.
 */
static bool fits(
	const std::vector<int>& x, const std::vector<int>& y,
	double ox, double oy, double r,
	std::initializer_list<std::size_t> taboo)
{
	const auto n = x.size();
	assert(n == y.size());
	auto t = taboo.begin();
	for(std::size_t i = 0; i != n; ++i) {
		if(t != taboo.end() && i == *t)
			++t;
		else if(r < std::hypot(x[i] - ox, y[i] - oy))
			return false;
	}
	return true;
}

static double radius(const std::vector<int>& x, const std::vector<int>& y) {
	const auto n = x.size();
	assert(n == y.size());
	double r = HUGE_VAL;
	for(std::size_t i = 0; i != n; ++i)
		for(std::size_t j = i + 1; j != n; ++j) {
			if(auto mr = std::hypot(x[i] - x[j], y[i] - y[j]) / 2; mr < r)
				if(auto [mx, my] = midpoint(x[i], y[i], x[j], y[j]);
				   fits(x, y, mx, my, mr, {i, j}))
					r = mr;
			for(std::size_t k = j + 1; k != n; ++k)
				if(auto [ux, uy, ur] = circumcircle(x[i], y[i], x[j], y[j], x[k], y[k]); ur < r)
					if(fits(x, y, ux, uy, ur, {i, j, k}))
						r = ur;
		}
	return r;
}

static double radius(const std::string& coordlist) {
	std::vector<int> x;
	std::vector<int> y;
	std::smatch m;
	static const std::regex point_pattern{R"(\((-?\d+),\s*(-?\d+)\))"};
	for(std::sregex_iterator p{coordlist.begin(), coordlist.end(), point_pattern}; p != std::sregex_iterator{}; ++p)
	{
		x.push_back(std::stoi((*p)[1].str()));
		y.push_back(std::stoi((*p)[2].str()));
	}
	return radius(x, y);
}

int main() {
	double sum = 0;
	for(std::string line; std::getline(std::cin, line); sum += radius(line));
	std::cout << static_cast<int>(sum) << '\n';
}