day15.cpp

#include <bits/stdc++.h>
#include <iostream>
#include <regex>
#include <cmath>


struct Point {
    int64_t x, y;
};

class Sensor : public Point {
public:
    int64_t length{};
    Point beacon{};

    explicit Sensor(const std::string& inputData) : Point() {
        std::smatch sm;
        std::regex regex(R"(^Sensor at x=(-?\d+), y=(-?\d+): closest beacon is at x=(-?\d+), y=(-?\d+))");
        std::regex_match(inputData, sm, regex);
        this->x = std::stoi(sm[1]);
        this->y = std::stoi(sm[2]);
        this->beacon.x = std::stoi(sm[3]);
        this->beacon.y = std::stoi(sm[4]);

        /**
         * determine length of the triangle covered by this sensor
         */
        int leftRightModifier(0);
        int upDownModifier(0);
        if (this->x > this->beacon.x) {
            leftRightModifier = 1;
        } else if (this->x < this->beacon.x) {
            leftRightModifier = -1;
        }
        if (this->y > this->beacon.y) {
            upDownModifier = -1;
        } else if (this->y < this->beacon.y) {
            upDownModifier = 1;
        }

        if (leftRightModifier == 0 || upDownModifier == 0) {
            // the beacon is on the same line as our sensor, so it is at the furthest point
            this->setLength(this->beacon);
        } else {
            int64_t x = this->beacon.x;
            int64_t y = this->beacon.y;
            while(x != this->x && y != this->y) {
                x += leftRightModifier;
                y += upDownModifier;
            }
            this->setLength({x, y});
        }
    }

    friend std::ostream & operator << (std::ostream &out, const Sensor &s) {
        out << "Sensor (" << s.x << ", " << s.y << ") " << "Beacon (" << s.beacon.x << ", " << s.beacon.y << ")" << " Length: " << s.length;
        return out;
    }

    /**
     * Checks if a point is inside this sensors range
     * @param point the Point to check
     */
    bool isInside(Point point) {
            auto const area = Sensor::triangleArea({this->x, this->y}, {this->x + this->length, this->y}, {this->x, this->y + this->length});

            Point positiveBase = {this->x + this->length, this->y};
            Point positiveHeight = {this->x, this->y + this->length};
            Point negativeBase = {this->x - this->length, this->y};
            Point negativeHeight = {this->x, this->y - this->length};

            // positive positive direction
            if (area == this->cumulativeArea(point, positiveBase, positiveHeight)) {
                return true;
            }

            // positive negative direction
            if (area == this->cumulativeArea(point, positiveBase, negativeHeight)) {
                return true;
            }

            // negative positive direction
            if (area == this->cumulativeArea(point, negativeBase, positiveHeight)) {
                return true;
            }

            // negative negative direction
            if (area == this->cumulativeArea(point, negativeBase, negativeHeight)) {
                return true;
            }

            return false;
    }

    /**
     * Calculate the area of a triangle given 3 points
     */
    static long double triangleArea(Point point1, Point point2, Point point3) {
        return std::abs((point1.x * (point2.y - point3.y) + point2.x * (point3.y - point1.y) + point3.x * (point1.y - point2.y)) / (long double)2.0);
    }

    long double cumulativeArea(Point point1, Point point2, Point point3) {
        auto area1 = Sensor::triangleArea(point1, point2, point3);
        auto area2 = Sensor::triangleArea({this->x, this->y}, point1, point3);
        auto area3 = Sensor::triangleArea({this->x, this->y}, point2, point1);
        return area1 + area2 + area3;
    }

private:
    void setLength(Point point) {
        this->length = (int64_t) std::sqrt(std::pow(this->x - point.x, 2) + std::pow(this->y - point.y, 2));
    }
};

int main()
{
    std::vector<Sensor> sensors;
    std::ifstream input ("input.txt");
    if (input.is_open()) {
        std::string readline;
        while (std::getline(input, readline)) {
            Sensor sensor(readline);
            sensors.emplace_back(sensor);
        }
    }

    int64_t maxX = 0;
    int64_t minX = 0;
    for (Sensor sensor : sensors) {
         if (sensor.x - sensor.length < minX) {
             minX = sensor.x - sensor.length;
         }
         if (sensor.x + sensor.length > maxX) {
             maxX = sensor.x + sensor.length;
         }
    }


    //int64_t y = 2000000;
    int64_t coveredLocations = 0;
    for (int64_t y = 0; y <= 4000000; ++y) {
        for (int64_t x = 0; x <= 4000000; ++x) {
        //for (int64_t x = minX; x <= maxX; ++x) {
            bool covered = false;
            std::string symbol = ".";
            for (Sensor sensor : sensors) {
                if ((sensor.x == x && sensor.y == y)) {
                    // this location cannot be covered because it's occupied by a sensor
                    covered = false;
                    symbol = "S";
                    break;
                } else if (sensor.beacon.x == x && sensor.beacon.y == y) {
                    // this location cannot be covered because it's occupied by a beacon
                    covered = false;
                    symbol = "B";
                    break;
                }
                if (sensor.isInside({x, y})) {
                    covered = true;
                    symbol = "#";
                }
            }
            if (covered) {
                coveredLocations++;
            } else {
                //std::cout << std::endl << x << " " << y << std::endl;
                std::cout << "(" << x << ", " << y << "): " << x * 4000000 + y << std::endl;
            }
            //std::cout << symbol;
        }
        uint64_t calculations = y * 4000000;
        if (calculations % 160000000 == 0) {
            std::cout << calculations << "/16000000000 " << std::fixed << std::setprecision(2)
                      << (calculations / (long double) 16000000000) * 100 << "%" << std::endl;
        }
    }
    //std::cout << std::endl << coveredLocations << std::endl;

    return 0;
}