C++

Correct answer in under 2 seconds, ie. about a hundred times longer than the rest of the puzzles so far combined. Can't think of a more efficient way to do this; no doubt it'll come to me at two in the morning, like usual.

Part 2 implementation breaks down the 'green tiles outline' into a series of line segments and then uses the even-odd winding rule to decide whether a point is inside or outside. Tracing the outline of the potential boxes to see whether the entirety is inside allows selection of the largest. We can skip tracing any potential box that wouldn't be bigger than what we have so far, and since the tests are easy to parallelise, have done so.

#include <atomic>
#include <boost/log/trivial.hpp>
#include <boost/unordered/concurrent_flat_map.hpp>
#include <cstddef>
#include <fstream>
#include <mutex>
#include <thread>

namespace {

struct Point {
  int x, y;
  auto operator+=(const Point &b) -> Point & {
    x += b.x;
    y += b.y;
    return *this;
  }
};

auto operator==(const Point &a, const Point &b) {
  return a.x == b.x && a.y == b.y;
}

auto operator!=(const Point &a, const Point &b) { return !(a == b); }

std::size_t hash_value(const Point &p) {
  return size_t(p.x) << 32 | size_t(p.y);
}

using Map = std::vector<Point>;
struct Line {
  Point a, b;
};

auto read() {
  auto rval = std::vector<Point>{};
  auto ih = std::ifstream{"09.txt"};
  auto line = std::string{};
  while (std::getline(ih, line)) {
    auto c1 = line.find(',');
    rval.emplace_back(
        std::stoi(line.substr(0, c1)), std::stoi(line.substr(c1 + 1))
    );
  }
  return rval;
}

auto size(const Point &a, const Point &b) -> uint64_t {
  size_t w = std::abs(a.x - b.x) + 1;
  size_t h = std::abs(a.y - b.y) + 1;
  return w * h;
}

auto part1(const std::vector<Point> &p) {
  auto maxi = std::size_t{};
  for (auto a = size_t{}; a < p.size() - 1; ++a)
    for (auto b = a + 1; b < p.size(); ++b)
      maxi = std::max(maxi, size(p[a], p[b]));
  return maxi;
}

auto make_line(const Point &a, const Point &b) {
  return Line{
      {std::min(a.x, b.x), std::min(a.y, b.y)},
      {std::max(a.x, b.x), std::max(a.y, b.y)}
  };
}

auto direction(const Point &a, const Point &b) {
  auto dx = b.x - a.x;
  auto dy = b.y - a.y;
  if (dx != 0)
    dx /= std::abs(dx);
  if (dy != 0)
    dy /= std::abs(dy);
  return Point{dx, dy};
}

// evaluates 'insideness' with the even-odd rule.  On the line -> inside
auto inside_uncached(const Point &a, const std::vector<Line> &lines) -> bool {
  auto even_odd = 0;
  for (const auto &line : lines) {
    if (line.a.y == line.b.y) { // horizontal
      if (a.y != line.a.y)
        continue;
      if (a.x <= line.a.x)
        continue;
      if (a.x < line.b.x)
        return true;
      even_odd += 1;
    } else { // vertical
      if (a.x < line.a.x)
        continue;
      if (a.y < line.a.y || a.y > line.b.y)
        continue;
      if (a.x == line.a.x)
        return true;
      even_odd += 1;
    }
  }
  return even_odd % 2 == 1;
}

using Cache = boost::unordered::concurrent_flat_map<Point, bool>;
auto cache = Cache{};

auto inside(const Point &a, const std::vector<Line> &lines) -> bool {
  std::optional<bool> o;
  bool found = cache.visit(a, [&](const auto &x) { o = x.second; });
  if (found)
    return o.value();
  auto b = inside_uncached(a, lines);
  cache.insert({a, b});
  return b;
}

auto inside(const Line &a, const std::vector<Line> &lines) -> bool {
  auto dir = direction(a.a, a.b);
  auto point = a.a;
  while (point != a.b) {
    point += dir;
    if (!inside(point, lines))
      return false;
  }
  return true;
}

auto part2(std::vector<Point> p) {
  auto outline = std::vector<Line>{};

  for (auto a = size_t{}; a < p.size() - 1; ++a)
    outline.push_back(make_line(p[a], p[a + 1]));
  outline.push_back(make_line(p.back(), p.front()));

  std::sort(outline.begin(), outline.end(), [](auto &a, auto &b) {
    return a.a.x < b.a.x;
  });

  std::sort(p.begin(), p.end(), [](auto &a, auto &b) {
    if (a.x != b.x)
      return a.x < b.x;
    return a.y > b.y;
  });

  auto maximum = std::atomic_uint64_t{};
  auto update_lock = std::mutex{};
  auto column_worker = std::atomic_uint64_t{};
  auto threadpool = std::vector<std::thread>{};

  for (auto t = size_t{}; t < std::thread::hardware_concurrency(); ++t) {
    threadpool.push_back(std::thread([&]() {
      while (true) {
        auto a = column_worker++;
        if (a > p.size() - 1)
          break;
        for (auto b = p.size() - 1; b > a; --b) {
          auto box = size(p[a], p[b]);

          // if it wouldn't be bigger, skip it
          if (box <= maximum)
            continue;

          // quick check for the opposite corners
          if (!inside(Point{p[a].x, p[b].y}, outline) ||
              !inside(Point{p[b].x, p[a].y}, outline))
            continue;

          // trace the outline
          auto left = make_line(p[a], Point{p[a].x, p[b].y});
          if (!inside(left, outline))
            continue;
          auto top = make_line(Point{p[a].x, p[b].y}, p[b]);
          if (!inside(top, outline))
            continue;
          auto right = make_line(Point{p[b].x, p[a].y}, p[b]);
          if (!inside(right, outline))
            continue;
          auto bottom = make_line(p[a], Point{p[b].x, p[a].y});
          if (!inside(bottom, outline))
            continue;

          // it's all on green tiles.  update as the biggest so far
          {
            auto _ = std::lock_guard<std::mutex>(update_lock);
            if (box > maximum)
              maximum = box;
          }
        }
      }
    }));
  }

  for (auto &thread : threadpool)
    thread.join();

  return uint64_t(maximum);
}

} // namespace

auto main() -> int {
  auto tiles = read();
  BOOST_LOG_TRIVIAL(info) << "Day 9: read " << tiles.size();
  BOOST_LOG_TRIVIAL(info) << "1: " << part1(tiles);
  BOOST_LOG_TRIVIAL(info) << "2: " << part2(tiles);
}