#include <cassert>
#include <cmath>
#include <optional>
#include <iostream>
#include <vector>

/*

Context
=======

This question is based on a real problem that we had to solve in production. There was a computationally
expensive algorithm implemented for generic polygons; however we have noticed that in the majority of
cases the polygon that we were passing to the algorithm was a rectangle, and for rectangles the
implementation of the algorithm was much faster.

Task
====

Implement a function that determines whether a given `Polygon` represents an axis-aligned rectangle, and
if so, returns a `Rectangle` which is equivalent.

You may assume:

- `Polygon` is a counter-clockwise oriented collection of points. This means the inside of the polygon
   would be on your left if you walked around the boundary following the points in the order provided
- `Polygon`, if not empty, is guaranteed to be cyclic, that is `polygon.front() == polygon.back()`
- `Polygon`, is not self-intersecting. This means that the edges between pairs of adjacent points in
  the polygon do not cross.

The `Polygon` may have been generated by other algorithms which suffer numerical instability problems so
your implementation should aim to be robust to degenerate cases. Some examples of degenerate cases that
your solution should handle are:

- Points lying on the straight edge connecting another pair of points a.k.a. redundant points
- Polygons with points slightly perturbed from exact rectangles should still convert to rectangles

Instructions
============

This is not a hackerrank exercise with a binary pass/fail result on the given tests. Take your time
to analyse the problem. Once you decide on an approach to solve the problem, make sure you are confident
with your understanding of its robustness and limitations. Think of edge cases that can stress test these
limitations and do not hesitate to write actual tests for them. Finally, please keep in mind that we
strongly value well-documented and readable code. For example, it may be helpful to write a paragraph in
the source file documenting your approach, the expected behaviour of your implementation and the key
assumptions you made regarding the input.

Submission
==========

Preserve the API of the `fit_into_rectangle` function (so we can easily run it through a test suite)

Submit your solution as a single .cpp file and provide the compilation command used to build it.
If you have been asked to submit your solution using codeinterview.io, you can make sure that your
solution builds and passes the tests by pressing the "Run" button at the bottom of the page

*/

constexpr float k_default_epsilon = .0001f;

bool almost_equal(float a, float b, float epsilon = k_default_epsilon) {
    return std::abs(a - b) <= epsilon;
}

struct Point {
    float x;
    float y;
    friend bool operator==(const Point& lhs, const Point& rhs) {
        return lhs.x == rhs.x and lhs.y == rhs.y;
    }
    friend std::ostream& operator<<(std::ostream& out, const Point& point) {
        return out << "(" << point.x << "," << point.y << ")";
    }
};

bool almost_equal(const Point& a, const Point& b, float epsilon = k_default_epsilon) {
    return almost_equal(a.x, b.x, epsilon) and almost_equal(a.y, b.y, epsilon);
}

using Polygon = std::vector<Point>;

struct Rectangle {
    Point bottom_left;
    Point top_right;
    friend std::ostream& operator<<(std::ostream& out, const Rectangle& rectangle) {
        return out << "Rectangle(" << rectangle.bottom_left << "," << rectangle.top_right << ")";
    }
};

bool almost_equal(const Rectangle& a, const Rectangle& b, float epsilon = k_default_epsilon) {
    return almost_equal(a.bottom_left, b.bottom_left, epsilon) and almost_equal(a.top_right, b.top_right, epsilon);
}

// ------------------------------------------------------------------------------------------------

const float MAX_VALUE = 0xFFFF;
const float MIN_VALUE = -0xFFFF;

/**
* Immutable struct that contains two points to represent a vector from p1 -> p2
*/
struct Vector {
    const float x;
    const float y;
    const Point origin;

    Vector(float x, float y) : x(x), y(y), origin({0, 0}) {}
    Vector(const Point& p1, const Point& p2) : x(p2.x - p1.x), y(p2.y - p1.y), origin(p1) {}

    float lengthSquared() const {
        return x * x + y * y;
    }

    float length() const {
        return sqrtf(lengthSquared());
    }

    // Returns the unit vector - vector with the same direction but length of 1
    Vector normalised() const {
        float len = length();
        return { x / len, y / len };
    }

    friend std::ostream& operator<<(std::ostream& out, const Vector& vec) {
        return out << "(" << vec.x << "," << vec.y << ")";
    }
};

/**
* Calculates the dot product of two vectors
*/
float dot(const Vector& v1, const Vector& v2) {
    return v1.x * v2.x + v1.y * v2.y;
}

/**
* Returns a list of Vector structs corresponding to the points of the polygon
*/
std::vector<Vector> get_vectors(const Polygon& polygon) {
    std::vector<Vector> vectors;

    for (std::size_t i = 1; i < polygon.size(); ++i) {
        vectors.push_back(Vector(polygon[i - 1], polygon[i]));
    }

    // Potentially expensive and slow copy
    return vectors;
}

std::optional<Rectangle> fit_into_rectangle(const Polygon& polygon, float epsilon = k_default_epsilon) {

    std::vector<Vector> vectors = get_vectors(polygon);

    bool is_rectangle = false;
    int num_right_angles = 0;
    Point bottom_left = { MAX_VALUE, MAX_VALUE };
    Point top_right = { MIN_VALUE, MIN_VALUE };

    // Cannot be rectangle if it's less than 4 points
    if (polygon.size() < 4) return std::nullopt;
    // Check that polygon ends in the same position as the start
    if (!almost_equal(*polygon.begin(), *(polygon.end() - 1)))
        return std::nullopt;

    // Loop through pairs of vectors and calculate dot product
    // Stop if number of right angles exceeds 4 because we know it cannot be a rectangle then
    for (std::size_t i = 0; i < vectors.size() && num_right_angles <= 4; ++i) {

        // Get the vector pairs - use last vector for v1 for first pair
        Vector v1 = i == 0 ? vectors[vectors.size() - 1] : vectors[i - 1];
        Vector v2 = vectors[i];

        // Calculate dot product
        float dot_product = dot(v1.normalised(), v2.normalised());

        bool is_right_angle = almost_equal(dot_product, 0);
        bool is_redundant = almost_equal(dot_product, 1);

        // If it's not a right angle and the vector pair isn't a straight line (redundant point) then early exit
        if (!is_right_angle && !is_redundant)
            break;

        if (is_right_angle) {
            // This vector pair makes a right-angle so find min/max points on each axis to determine bottom_left and top_right
            // The point in interest is between the end point of v1 or start point of v2
            if (v2.origin.x < bottom_left.x)
                bottom_left.x = v2.origin.x;
            if (v2.origin.y < bottom_left.y)
                bottom_left.y = v2.origin.y;

            if (v2.origin.x > top_right.x)
                top_right.x = v2.origin.x;
            if (v2.origin.y > top_right.y)
                top_right.y = v2.origin.y;

            num_right_angles++;
        }
    }

    // Rectangles must have 4 right angles
    is_rectangle = num_right_angles == 4;

    // The question asks only for a Rectangle object if it is axis-aligned
    if (is_rectangle)
    {
        Rectangle rect{bottom_left, top_right};
        return std::make_optional<Rectangle>(rect);
    }
    else
        return std::nullopt;
}

// ----------------- UNIT TESTS -----------------
void test_vector() {
    {
        // Classic a^2 + b^2 = c^2 case with sides 3 4 5
        Point p1 = { 2,3 };
        Point p2 = { 5,7 };
        Vector v(p1, p2);

        assert(v.length() == 5);
        assert(v.x == 3);
        assert(v.y == 4);
    }
    {
        // Points with negative values
        Point p1 = { -30,-5 };
        Point p2 = { -10,-26 };
        Vector v(p1, p2);

        assert(v.length() == 29);
        assert(v.x == 20);
        assert(v.y == -21);
    }
    {
        // Points with floating point imprecision
        Point p1 = { 0, 0 };
        Point p2 = { 1, 2 };
        Vector v(p1, p2);

        assert(almost_equal(v.length(), 2.236067f));
    }
}

void test_dot_product() {
    {
        // Vectors in the same direction and same magnitude - expect dot product of 1
        Vector v1 = Vector({ 0, 0 }, { 1, 2 });
        Vector v2 = Vector({ 0, 0 }, { 1, 2 });
        assert(almost_equal(dot(v1.normalised(), v2.normalised()), 1));
    }
    {
        // Vectors in the same direction and same magnitude - expect dot product of 1
        Vector v1 = Vector({ 2, 1 }, { 4, 4 });
        Vector v2 = Vector({ 6, 8 }, { 8, 11 });
        assert(almost_equal(dot(v1.normalised(), v2.normalised()), 1));
    }
    {
        // Vectors in the same direction with different magnitudes - dot product of unit vectors, expect value of 1
        Vector v1 = Vector({ 0, 0 }, { 4, 4 });
        Vector v2 = Vector({ 0, 0 }, { 8, 8 });
        assert(almost_equal(dot(v1.normalised(), v2.normalised()), 1));
    }
    {
        // Axis-aligned vectors at right angles
        Vector v1 = Vector({ 0, 0 }, { 5, 0 });
        Vector v2 = Vector({ 0, 0 }, { 0, 5 });
        assert(almost_equal(dot(v1, v2), 0));
    }
    {
        // Not axis-aligned vectors at right angles
        Vector v1 = Vector({ 0, 0 }, { 5, 5 });
        Vector v2 = Vector({ 0, 0 }, { 5, -5 });
        assert(almost_equal(dot(v1, v2), 0));
    }
    {
        // Dot product of vectors with random values
        Vector v1 = Vector({ 5, 1 }, { 9, 8 });
        Vector v2 = Vector({ 4, 3 }, { 2, 10 });
        assert(almost_equal(dot(v1, v2), 41));
        assert(almost_equal(dot(v1.normalised(), v2.normalised()), 0.69853));
    }
}

void run_unit_tests() {
    test_vector();
    test_dot_product();
}

int main() {

    run_unit_tests();

    {
        // Case 1: a well formed rectangle
        //   *------*
        //   |      |
        //   |      |
        //   |      |
        //   *------*
        const Polygon polygon({ {6,1},{6,4},{1,4},{1,1},{6,1} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(rectangle);
        assert(almost_equal(*rectangle, Rectangle{ {1,1},{6,4} }));
    }

    {
        // Case 2: a polygon with redundant points
        //   *--*---*
        //   |      |
        //   |      *
        //   |      |
        //   *------*
        const Polygon polygon({ {6,3},{6,5},{3,5},{1,5},{1,1},{6,1},{6,3} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(rectangle);
        assert(almost_equal(*rectangle, Rectangle{ {1,1},{6,5} }));
    }

    {
        // Case 3: a polygon with a diagonal edge
        //   *------*
        //   |       `
        //   |        `
        //   |         `
        //   *----------*
        const Polygon polygon({ {1,1},{10,1},{6,5},{1,5},{1,1} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(not rectangle);
    }

    {
        // Case 4: a polygon with axis-aligned edges, but non-rectangular shape
        //   *------*
        //   |      |
        //   |      *---*
        //   |          |
        //   *----------*
        const Polygon polygon({ {1,1},{10,1},{10,3},{6,3},{6,5},{1,5},{1,1} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(not rectangle);
    }

    {
        // Case 5: a non-axis-aligned rectangle
        //      /\
        //     /  \
        //    /   /
        //    \  /
        //     \/
        const Polygon polygon({ {4,1},{8,5},{5,8},{1,4},{4,1} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(rectangle);
    }

    {
        // Case 6: a polygon with slightly perturbed points, this is bread-and-butter in computational geometry
        //   *------*
        //   |      |
        //   |      |
        //   |      |
        //   *------~
        const Polygon polygon({ {1,1},{6,1.00001},{6,4},{1,4},{1,1} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(rectangle);
        assert(almost_equal(*rectangle, Rectangle{ {1,1},{6,4} }));
    }

    // ---------- My tests ----------

    {
        // Case 7: a polygon that does not make a complete shape but all right-angles
        //   *------*
        //          |
        //          |
        //          |
        //          *------~
        const Polygon polygon({ {1,6},{6,6},{6,1},{12,1} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(not rectangle);
    }

    {
        // Case 8: a polygon that has all right-angles but is not a rectangle
        //   *------*
        //   |      |
        //   |   *--*
        //   |   |  |
        //   |   |  |
        //   |   *--*
        //   |      |
        //   *------*
        const Polygon polygon({ {1,6},{1,1},{6,1},{6,2},{5,2},{5,4},{6,4},{6,6},{1,6} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(not rectangle);
    }

    {
        // Case 9: a polygon with all slightly perturbed points
        //   ~------~
        //   |      |
        //   |      |
        //   |      |
        //   ~------~
        const Polygon polygon({ {0.99999,1.00001},{5.99999,1.00001},{6.00001,3.99999},{1.00001,3.99999},{1.00001,0.99999} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(rectangle);
        assert(almost_equal(*rectangle, Rectangle{ {1,1},{6,4} }));
    }

    {
        // Case 10: a polygon with many redundant points
        //   *--**--*
        //   |      |
        //   *      |
        //   |      |
        //   *-****-*
        const Polygon polygon({ {1,6}, {1,3}, {1,1}, {2,1}, {3,1}, {4,1}, {6,1}, {6,6}, {4,6}, {3,6}, {1,6} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(rectangle);
        assert(almost_equal(*rectangle, Rectangle{ {1,1},{6,6} }));
    }

    {
        // Case 11: Empty polygon
        const Polygon polygon({ });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(not rectangle);
    }

    {
        // Case 11: Triangle
        const Polygon polygon({ {0,0}, {1,1}, {0, 1}, {0,0} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(not rectangle);
    }

    {
        // Case 11: Incomplete polygon
        const Polygon polygon({ {0,0}, {1,1}, {0, 1} });
        const auto rectangle = fit_into_rectangle(polygon);
        assert(not rectangle);
    }

    return 0;
}