-
-
Save i4kp3e/a77ba6fea0d19faaf8a1ff4c551e9a4a to your computer and use it in GitHub Desktop.
Solution to "Infi - Advent of Code 2023" on https://aoc.infi.nl/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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'; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment