#pragma once

#include <vector>
#include <utility>
#include <iostream>
#include <cassert>

#include "vec2.hpp"

template <typename T>
int orientation(vec2<T> p1, vec2<T> p2, vec2<T> p3) {
    T val = (p2.y - p1.y) * (p3.x - p2.x) -
            (p2.x - p1.x) * (p3.y - p2.y);
    if (val == 0) return 0;
    if (val < 0) return -1;
    return 1;
}

/* p has to be coolinear to the segment s */
template <typename T>
bool on_segment(std::pair<vec2<T>, vec2<T>> s, vec2<T> p) {
    if (p.x <= std::max(s.first.x, s.second.x) && p.x >= std::min(s.first.x, s.second.x) &&
        p.y <= std::max(s.first.y, s.second.y) && p.y >= std::min(s.first.y, s.second.y)) {
        return true;
    }
    return false;
}

template <typename T>
std::vector<vec2<T>>
intersect(std::pair<vec2<T>, vec2<T>> l1, std::pair<vec2<T>,vec2<T>> l2) {
    if (l2 < l1) {
        std::swap(l1, l2);
    }

    auto [p1, p2] = l1;
    auto [p3, p4] = l2;

    if ( cross((p2 - p1), (p4 - p3)) == T(0l)) {
        if (orientation(p1, p3, p2)) {
            return {};
        }

        auto v1 = p2 - p1;
        T denom =  dot(p2 - p1, p2 - p1);
        T alpha1 = dot(p3 - p1, p2 - p1);
        T alpha2 = dot(p4 - p1, p2 - p1);
        if (alpha1 > alpha2) {
            std::swap(alpha1, alpha2);
        }
        //check if segments overlap
        std::pair<T, T> isec = { std::max(T(0), alpha1),
                                 std::min(denom, alpha2)};
        if (isec.second < isec.first) return {};
        if (isec.first == isec.second)
            return {p1 + (isec.first/denom) * v1};

        return {p1 + (isec.first/ denom) * v1,
                p1 + (isec.second / denom) * v1};
    } else {
        /* find t and u*/
        T t(cross((p4 - p1), (p4 - p3)).numer, cross((p2 - p1), (p4 - p3)).numer);
        T s(cross((p2 - p3), (p2 - p1)).numer, cross((p4 - p3), (p2 - p1)).numer);
        auto v1 = p2 - p1;
        //check if s and t is between 0 and 1
        if (t < T(0l) || t > T(1l)) return {};
        if (s < T(0l) || s > T(1l)) return {};

        return {p3 + s * (p4 - p3)};
    }
}