aoc 2025 p9

#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

#define ll long long

std::vector<string> split(std::string& s, std::string&& delim) {
    std::vector<string> tokens;
    int start = 0;
    int end;
    while( (end = s.find(delim, start)) != string::npos) {
        tokens.push_back(s.substr(start, end - start));
        start = end + delim.length();
    }
    if(start < s.length()) {
        tokens.push_back(s.substr(start));
    }
    return tokens;
}

struct Pair {
    ll x;
    ll y;
    bool operator==(const Pair& other) const {
        return x == other.x && y == other.y;
    }
    friend std::ostream& operator<<(std::ostream& os, const Pair& p) {
        os << "(" << p.x << ", " << p.y << ")";
        return os;
    }
};

ll solve(std::vector<Pair> pairs) {
    ll ans = 0;
    for(int i=0; i<pairs.size(); i++) {
        for(int j=i+1; j<pairs.size(); j++) {
            ll s1 = std::abs(pairs[i].x - pairs[j].x) + 1;
            ll s2 = std::abs(pairs[i].y - pairs[j].y) + 1;
            ans = std::max(ans, s1 * s2);
        }
    }
    return ans;
}

void drawLine(Pair& p1, Pair& p2, std::unordered_map<int, ll>& xCompression, std::unordered_map<int, ll>& yCompression, std::vector<std::vector<ll>>& grid) {
    auto startX = std::min(xCompression[p1.x], xCompression[p2.x]);
    auto endX = std::max(xCompression[p1.x], xCompression[p2.x]);
    auto startY = std::min(yCompression[p1.y], yCompression[p2.y]);
    auto endY = std::max(yCompression[p1.y], yCompression[p2.y]);
    if(startX == endX) {
        for(int i=startY; i<=endY; i++) {
            grid[i][startX] = 2;
        }
        grid[endY][startX] = 1;
    }
    else {
        for(int i=startX; i<=endX; i++) {
            if(grid[startY][i] == 0) {
                grid[startY][i] = 1;
            }
        }
    }
}
/*
We use day 9 visualizer to see that the polygon has no crossing intersections. Thus when validating a rectangle, we simple need to check whether
any side of the rectangle intersects with a line segment contained on the border of the polygon.
*/
ll solve2(std::vector<Pair>& pairs) {
    std::unordered_map<int, ll> xCompression;
    std::unordered_map<int, ll> yCompression;
    std::unordered_map<ll,int> revX;
    std::unordered_map<ll,int> revY;
    std::vector<ll> xCoordinates;
    std::vector<ll> yCoordinates;
    for(const auto& pair : pairs) {
        xCoordinates.push_back(pair.x);
        yCoordinates.push_back(pair.y);
    }
    int xIndex = 0;
    int yIndex = 0;
    int xMax = 0;
    int yMax = 0;
    std::sort(xCoordinates.begin(), xCoordinates.end());
    std::sort(yCoordinates.begin(), yCoordinates.end());
    for(int i=0; i<xCoordinates.size(); i++) {
        int currX = xCoordinates[i];
        int currY = yCoordinates[i];
        if(!xCompression.contains(currX)) {
            xCompression[currX] = xIndex;
            revX[xIndex++] = currX;
        }
        if(!yCompression.contains(currY)) {
            yCompression[currY] = yIndex;
            revY[yIndex++] = currY;
        }
        xMax = std::max(xIndex, xMax);
        yMax = std::max(yIndex, yMax);

    }
    std::vector<std::vector<ll>> grid(yMax, std::vector<ll>(xMax,0));
    for(int i=0; i<pairs.size(); i++) {
        if(i < pairs.size() - 1) {
            drawLine(pairs[i], pairs[i+1],xCompression, yCompression, grid);
        }
        else {
            drawLine(pairs[i], pairs[0],xCompression, yCompression, grid);
        }
    }
    // Now fill the shape
    for(int row = 0; row<grid.size(); row++) {
        int parity = 0;
        for(int col = 0; col < grid[0].size(); col++) {
            if(grid[row][col] == 2) {
                parity ^= 1;
            }
            else if(parity == 1) {
                grid[row][col] = 1;
            }
        }
    }
    // Compute prefix sums for columns to see how far we can extend
    std::vector<std::vector<ll>> colSums(grid.size(), std::vector<ll>(grid[0].size(), 0));
    for(int col = 0; col < grid[0].size(); col++) {
        ll startSquare = -1;
        for(int row = 0; row<grid.size(); row++) {
            if(grid[row][col] == 0) {
                startSquare = -1;
            }
            else {
                if(startSquare == -1) {
                    startSquare = revY[row];
                }
                colSums[row][col] = revY[row] - startSquare + 1;
            }
        }
    }

    ll ans = 1;
    for(int i=0; i<pairs.size(); i++) {
        for(int j=i+1; j<pairs.size(); j++) {
            bool canUse = true;
            auto& startPoint = pairs[i];
            auto& endPoint = pairs[j];
            if(startPoint.y < endPoint.y) {
                const auto& tmp = startPoint;
                startPoint = endPoint;
                endPoint = tmp;
            }
            auto needHeight = std::abs(endPoint.y - startPoint.y) + 1;
            auto xCompStart = xCompression[startPoint.x];
            auto xCompEnd = xCompression[endPoint.x];
            auto yCompStart = yCompression[startPoint.y];
            if(xCompStart < xCompEnd) {
                for(int col = xCompStart; col<=xCompEnd; col++) {
                    if(grid[yCompStart][col] == 0 || colSums[yCompStart][col] < needHeight) {
                        canUse = false;
                        break;
                    }
                }
            }
            else {
                for(int col = xCompStart; col>=xCompEnd; col--) {
                    if(grid[yCompStart][col] == 0 || colSums[yCompStart][col] < needHeight) {
                        canUse = false;
                        break;
                    }
                }
            }
            if(canUse) {
                auto s1 = std::abs(endPoint.x - startPoint.x) + 1;
                auto s2 = std::abs(endPoint.y - startPoint.y) + 1;
                ans = std::max(ans, s1 * s2);
            }
        }
    }
    return ans;
}

int main() {
    ifstream inputFile("../data/day9.txt");
    std::string line;
    std::vector<Pair> pairs;
    while(std::getline(inputFile, line)) {
        vector<string> pairStrs = split(line, ",");
        pairs.emplace_back(std::stoull(pairStrs[0]), std::stoull(pairStrs[1]));
    }
    std::cout << solve2(pairs) << std::endl;
    return 0;
}