aoc(2318): Lavaduct Lagoon

1 files changed, 39 insertions, 0 deletions

diff --git a/2023/include/util.h b/2023/include/util.h
index e396e3c..3152719 100644
--- a/2023/include/util.h
+++ b/2023/include/util.h
@@ -6,6 +6,7 @@
 #include <stdexcept>
 #include <string>
 #include <string_view>
+#include <type_traits>
 
 namespace util
 {
@@ -119,6 +120,44 @@ std::basic_istream<CharT, Traits>& skip(std::basic_istream<CharT, Traits>& strea
     return stream;
 }
 
+/* @brief Compute the area of a planar simple polygon.
+ *
+ * @tparam Int integral coordinate type.
+ * @param first start of an iterator over pairs of 'Int'.
+ * @param last end of an iterator over pairs of 'Int'.
+ *
+ * @see https://en.wikipedia.org/wiki/Shoelace_formula#Triangle_formula
+ */
+template<typename Int, typename InputIt, typename = std::enable_if_t<std::is_integral_v<Int>,Int>>
+Int shoelace(InputIt first, InputIt last)
+{
+    Int result{};
+    auto [x1, y1] = *first;
+    while(first++ != last)
+    {
+        auto [x2, y2] = *first;
+        result += x1 * y2 - x2 * y1;
+        x1 = x2; y1 = y2;
+    }
+    return std::abs(result / 2);
+}
+
+/* @brief Return the number of integral coordinates inside a planar
+ *        simple polygon.
+ *
+ * @tparam Int integral return type.
+ * @param area the area of the polygon.
+ * @param border the number of integral coordinates on the polygon's
+ *        boundary.
+ * 
+ * @see https://en.wikipedia.org/wiki/Pick%27s_theorem#Formula
+ */
+template<typename Int = int, typename = std::enable_if_t<std::is_integral_v<Int>,Int>>
+Int pick(Int area, Int border)
+{
+    return area - border / 2 + 1;
+}
+
 } // namespace util
 
 #endif //UTIL_H