test/Geometry/point/aoj-CGL_1_C.cpp

View this file on GitHub
Last update: 2024-11-05 00:49:00+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C

Depends on

Geometry/point.hpp

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C

#include "Geometry/point.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long xp0, yp0, xp1, yp1;
    cin >> xp0 >> yp0 >> xp1 >> yp1;
    Point<long long> p0(xp0, yp0), p1(xp1, yp1);

    int q;
    cin >> q;

    for (int i = 0; i < q; i++)
    {
        long long xpi, ypi;
        cin >> xpi >> ypi;
        Point<long long> pi(xpi, ypi);

        Point<long long>::CCWResult ccw = Point<long long>::ccw(p0, p1, pi);
        if (ccw == Point<long long>::CCWResult::COUNTER_CLOCKWISE)
        {
            cout << "COUNTER_CLOCKWISE" << endl;
        }
        else if (ccw == Point<long long>::CCWResult::CLOCKWISE)
        {
            cout << "CLOCKWISE" << endl;
        }
        else if (ccw == Point<long long>::CCWResult::ON_LINE_BACK)
        {
            cout << "ONLINE_BACK" << endl;
        }
        else if (ccw == Point<long long>::CCWResult::ON_LINE_FRONT)
        {
            cout << "ONLINE_FRONT" << endl;
        }
        else if (ccw == Point<long long>::CCWResult::ON_SEGMENT)
        {
            cout << "ON_SEGMENT" << endl;
        }
    }

    return 0;
}

#line 1 "test/Geometry/point/aoj-CGL_1_C.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C

#line 1 "Geometry/point.hpp"
#include <bits/stdc++.h>
using namespace std;

template <class T, typename = enable_if_t<is_arithmetic_v<T>>>
class Point
{
    complex<T> coordinate;
    static constexpr long double EPS = 1e-8;

public:
    Point() {}

    Point(T x, T y) : coordinate(x, y) {}

    Point(complex<T> coordinate) : coordinate(coordinate) {}

    T real() const { return coordinate.real(); }
    T imag() const { return coordinate.imag(); }
    T norm() const { return std::norm(coordinate); }

    static T dot(const Point &a, const Point &b)
    {
        return a.real() * b.real() + a.imag() * b.imag();
    }

    static T cross(const Point &a, const Point &b)
    {
        return a.real() * b.imag() - a.imag() * b.real();
    }

    Point operator+(const Point &other) const
    {
        return Point(this->coordinate + other.coordinate);
    }

    Point operator-(const Point &other) const
    {
        return Point(this->coordinate - other.coordinate);
    }

    Point operator*(const Point &other) const
    {
        return Point(this->coordinate * other.coordinate);
    }

    Point operator/(const Point &other) const
    {
        return Point(this->coordinate / other.coordinate);
    }

    bool operator<(const Point &other) const
    {
        if (this->real() != other.real())
            return this->real() < other.real();
        return this->imag() < other.imag();
    }

    enum class CCWResult
    {
        COUNTER_CLOCKWISE = 2,
        CLOCKWISE = -2,
        ON_LINE_BACK = 1,
        ON_LINE_FRONT = -1,
        ON_SEGMENT = 0
    };

    static CCWResult ccw(const Point &a, Point b, Point c)
    {
        b.coordinate = b.coordinate - a.coordinate, c.coordinate = c.coordinate - a.coordinate;
        if (cross(b, c) > Point::EPS)
            return CCWResult::COUNTER_CLOCKWISE;
        if (cross(b, c) < -Point::EPS)
            return CCWResult::CLOCKWISE;
        if (dot(b, c) < 0)
            return CCWResult::ON_LINE_BACK;
        if (b.norm() < c.norm())
            return CCWResult::ON_LINE_FRONT;
        return CCWResult::ON_SEGMENT;
    }
};
#line 5 "test/Geometry/point/aoj-CGL_1_C.cpp"

using namespace std;

int main()
{
    long long xp0, yp0, xp1, yp1;
    cin >> xp0 >> yp0 >> xp1 >> yp1;
    Point<long long> p0(xp0, yp0), p1(xp1, yp1);

    int q;
    cin >> q;

    for (int i = 0; i < q; i++)
    {
        long long xpi, ypi;
        cin >> xpi >> ypi;
        Point<long long> pi(xpi, ypi);

        Point<long long>::CCWResult ccw = Point<long long>::ccw(p0, p1, pi);
        if (ccw == Point<long long>::CCWResult::COUNTER_CLOCKWISE)
        {
            cout << "COUNTER_CLOCKWISE" << endl;
        }
        else if (ccw == Point<long long>::CCWResult::CLOCKWISE)
        {
            cout << "CLOCKWISE" << endl;
        }
        else if (ccw == Point<long long>::CCWResult::ON_LINE_BACK)
        {
            cout << "ONLINE_BACK" << endl;
        }
        else if (ccw == Point<long long>::CCWResult::ON_LINE_FRONT)
        {
            cout << "ONLINE_FRONT" << endl;
        }
        else if (ccw == Point<long long>::CCWResult::ON_SEGMENT)
        {
            cout << "ON_SEGMENT" << endl;
        }
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_int_00.in	AC	5 ms	3 MB
g++	00_int_01.in	AC	4 ms	3 MB
g++	00_int_02.in	AC	4 ms	3 MB
g++	00_int_03.in	AC	4 ms	3 MB
g++	00_int_04.in	AC	5 ms	3 MB
g++	00_int_05.in	AC	4 ms	3 MB
g++	01_real_00.in	AC	4 ms	3 MB
g++	01_real_01.in	AC	4 ms	3 MB
g++	02_online_00.in	AC	4 ms	3 MB
g++	02_online_01.in	AC	4 ms	3 MB
g++	02_online_02.in	AC	4 ms	3 MB
g++	02_online_03.in	AC	4 ms	3 MB
g++	03_horizontal_00.in	AC	5 ms	3 MB
g++	03_horizontal_01.in	AC	5 ms	3 MB
g++	04_vertical_00.in	AC	5 ms	3 MB
g++	04_vertical_01.in	AC	5 ms	3 MB
g++	05_rand_00.in	AC	5 ms	3 MB
g++	05_rand_01.in	AC	5 ms	3 MB
g++	05_rand_02.in	AC	5 ms	3 MB
g++	05_rand_03.in	AC	6 ms	3 MB
g++	05_rand_04.in	AC	6 ms	3 MB
g++	05_rand_05.in	AC	6 ms	3 MB
g++	05_rand_06.in	AC	6 ms	3 MB
g++	05_rand_07.in	AC	6 ms	3 MB
g++	05_rand_08.in	AC	6 ms	3 MB
g++	05_rand_09.in	AC	7 ms	3 MB
g++	05_rand_10.in	AC	7 ms	3 MB
g++	05_rand_11.in	AC	7 ms	3 MB
g++	06_online_00.in	AC	7 ms	3 MB
g++	06_online_01.in	AC	6 ms	3 MB
g++	07_extreme_00.in	AC	4 ms	3 MB
g++	07_extreme_01.in	AC	4 ms	3 MB