378 - Intersecting Lines

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define multi_ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define endl "\n"
#define MOD 1000000007
#define INF 2000000000
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define sz(x) int(x.size())
#define crossProd(A,B) ((conj(A)*(B)).imag())
#define dotProd(A,B) ((conj(A)*(B)).real())

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define EPS 1e-9
#define PI acos(-1)
#define X real()
#define Y imag()
#define normalize(a) (a) / length(a)
#define lengthSqr(p) dot_prod(p, p)
#define rotateO(p, ang) p * exp(point(0, ang))
#define rotateA(p, about, ang) rotateO(vector((about), (p)), ang) + (about)
#define reflicatO(v, m) conj(v / m) * m
#define reflicatA(v, about, m) conj(vector(about, v) / vector(about, m)) * vector(about, m) + about

template<typename T>
class point {
public:
    T x, y;
    point() {
        x = y = 0;
    }
    point(T _x, T _y) {
        x = _x;
        y = _y;
    }
    point(const point<T> &p) {
        x = p.x;
        y = p.y;
    }
    // vector from point a to point b
    point(const point<T> &a, const point<T> &b) {
        *this = b - a;
    }
    point operator=(const point<T> &p) {
        x = p.x;
        y = p.y;
        return *this;
    }
    point operator+(const point<T> &p) const {
        return point(x + p.x, y + p.y);
    }
    point operator-(const point<T> &p) const {
        return point(x - p.x, y - p.y);
    }
    // dot product
    T operator*(const point<T> &p) const {
        return x * p.x + y * p.y;
    }
    // cross product
    T operator^(const point<T> &p) const {
        return x * p.y - y * p.x;
    }
    point operator*(const T &factor) const {
        return point(x * factor, y * factor);
    }
    point operator/(const T &factor) const {
        return point(x / factor, y / factor);
    }
    friend istream &operator>>(istream &is, point<T> &p) {
        is >> p.x >> p.y;
        return is;
    }
    friend ostream &operator<<(ostream &os, const point<T> &p) {
        os << p.x << " " << p.y;
        return os;
    }
    bool operator==(const point<T> &p) const {
        return (x == p.x && y == p.y);
    }
    bool operator!=(const point<T> &p) const {
        return (x != p.x || y != p.y);
    }
    ld arg() const {
        return atan2l(y, x);
    }
    T lenSqr() const {
        return x * x + y * y;
    }
    double len() const {
        return hypot(x, y);
    }
    // distance
    double dist(const point<T> &p) const {
        return hypot(x - p.x, y - p.y);
    }
    // distance squared
    T distSqr(const point<T> &p) const {
        return (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y);
    }
    // returns 1 for counterclockwise order
    // returns -1 for clockwise order
    // returns 0 if the points are collinear
    int orientation(const point<T> &p, const point<T> &q) const {
        T val = (q - p) ^ (*this - q);
        if (val == 0)
            return 0;
        return (val > 0) ? 1 : -1;
    }
    // check intersection between line segment p1q1 and line segment p2q2
    static bool intersect_ab_cd(point<T> a, point<T> b, point<T> c, point<T> d, point<T> &intersect) {
        point<T> u(a, b);
        point<T> v(c, d);
        point<T> w(c, a);
        T d1 = u ^ v;
        T d2 = v ^ w;
        T d3 = u ^ w;
        if (d1 == 0)
            return false;
        double t1 = d2 / d1;
        double t2 = d3 / d1;
        intersect = a + u * t1;
        return true; // e.g ab is a line, cd is a line
        // return t1 >= EPS && t2 >= EPS && t2 <= 1 + EPS; // e.g ab is a ray, cd is a segment
    }
};

// ab segment, c point
double segPointDist(point<double> a, point<double> b, point<double> c, point<double> &ans) {
    point<double> u(a, b), v(b, c), w(a, c);
    double d1, d2;
    if ((d1 = w * u) < -EPS) {
        ans = a;
        return a.dist(c);
    }
    if ((d2 = u * u) <= d1) {
        ans = b;
        return b.dist(c);
    }
    double t = d1 / d2;
    ans = a + u * t;
    return ans.dist(c);
}

void solve() { // NONE, LINE, POINT
    cout << fixed << setprecision(2);
    vector<point<double>> ps(4);
    for (auto& p : ps)
        cin >> p;
    point<double> intersect;
    if (point<double>::intersect_ab_cd(ps[0], ps[1], ps[2], ps[3], intersect)) {
        cout << "POINT " << intersect << endl;
    } else if (ps[0].orientation(ps[1], ps[2]) == 0) {
        cout << "LINE" << endl;
    } else {
        cout << "NONE" << endl;
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int testcase = 1;
    cin >> testcase;
    cout << "INTERSECTING LINES OUTPUT" << endl;
    while (testcase--)
        solve();
    cout << "END OF OUTPUT" << endl;
    return 0;
}