#include <filesystem>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <tuple>

using namespace std;

namespace {

using Point = tuple<int, int>;

set<Point>
read_file(const filesystem::path& filename)
{
	ifstream   file{ filename };
	set<Point> points;

	int  x{};
	int  y{};
	char sep{};

	while ( file >> x >> sep >> y ) {
		points.insert({ x, y });
	}

	return points;
}

void
getBoundingBox(const set<Point>& points, Point& topLeft, Point& bottomRight)
{
	auto minX = numeric_limits<int>::max();
	auto minY = numeric_limits<int>::max();
	auto maxX = numeric_limits<int>::min();
	auto maxY = numeric_limits<int>::min();

	for ( const auto [x, y]: points ) {
		minX = min(minX, x);
		minY = min(minY, y);
		maxX = max(maxX, x);
		maxY = max(maxY, y);
	}

	topLeft     = { minX, minY };
	bottomRight = { maxX, maxY };
}

int
manhattanDistance(const Point& lhs, const Point& rhs)
{
	int distance = abs(get<0>(lhs) - get<0>(rhs)) + abs(get<1>(lhs) - get<1>(rhs));

	return distance;
}

void
part1(const set<Point>& points)
{
	Point topLeft{};
	Point bottomRight{};
	getBoundingBox(points, topLeft, bottomRight);

	const auto [minX, minY] = topLeft;
	const auto [maxX, maxY] = bottomRight;

	map<Point, int> areaCount;
	set<Point>      infinite;

	static const int offset = 1;

	for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) {
		for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) {
			int   bestDistance = numeric_limits<int>::max();
			Point bestPoint{};
			bool  tie = false;

			for ( const auto& point: points ) {
				int distance = manhattanDistance(point, { posX, posY });
				if ( distance < bestDistance ) {
					bestDistance = distance;
					bestPoint    = point;
					tie          = false;
				}
				else if ( distance == bestDistance ) {
					tie = true;
				}
			}

			if ( !tie ) {
				areaCount[bestPoint]++;

				if ( posX < minX || posX > maxX || posY < minY || posY > maxY ) {
					infinite.insert(bestPoint);
				}
			}
		}
	}

	int maxSize = 0;
	for ( const auto& [point, size]: areaCount ) {
		if ( infinite.contains(point) ) {
			continue;
		}
		maxSize = max(maxSize, size);
	}

	cout << "Part 1: " << maxSize << '\n';
}

void
part2(const set<Point>& points, const int threshold)
{
	Point topLeft{};
	Point bottomRight{};
	getBoundingBox(points, topLeft, bottomRight);

	const auto [minX, minY] = topLeft;
	const auto [maxX, maxY] = bottomRight;

	static const int offset = 100;

	unsigned int regionSize = 0;

	for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) {
		for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) {
			int sum = 0;

			for ( const auto& point: points ) {
				int distance = manhattanDistance(point, { posX, posY });
				sum += distance;
			}

			if ( sum < threshold ) {
				++regionSize;
			}
		}
	}

	cout << "Part 2: " << regionSize << '\n';
}

} // namespace

int
main()
{
	auto points = read_file("data/day06.txt");
	part1(points);
	part2(points, 10000);
}