テンプレート

使い方

基本的には long double を使い eps も小さめにする． $\mathrm{ccw}(A,B,C)$ は点 $A$, $B$ に対し，$C$ が以下のどの位置にあるのか調べる．

$A,B,C$ が半時計回りの三角形を作る
$A,B,C$ が時計回りの三角形を作る
$C,A,B$ の順に一直線に並ぶ
$A,B,C$ の順に一直線に並ぶ
$A,C,B$ の順に一直線に並ぶ

実装

using ld = long double;
using P = std::complex<ld>;
using G = std::vector<P>;
const ld pi = std::acos(-1);
const ld eps = 1e-10;
const ld inf = 1e12;

ld cross(const P &a, const P &b) { return a.real() * b.imag() - a.imag() * b.real(); }
ld dot(const P &a, const P &b) { return a.real() * b.real() + a.imag() * b.imag(); }

/*
                    CCW

 -- BEHIND -- [a -- ON -- b] --- FRONT --

                    CW
 */
enum CCW_RESULT { CCW = +1, CW = -1, BEHIND = +2, FRONT = -2, ON = 0 };
int ccw(P a, P b, P c) {
    b -= a;
    c -= a;
    if (cross(b, c) > eps) return CCW;    // counter clockwise
    if (cross(b, c) < -eps) return CW;    // clockwise
    if (dot(b, c) < 0) return BEHIND;     // c--a--b on line
    if (norm(b) < norm(c)) return FRONT;  // a--b--c on line
    return ON;
}

namespace std {
bool operator<(const P &a, const P &b) {
    return std::abs(real(a) - real(b)) > eps ? real(a) < real(b) : imag(a) < imag(b);
}
}

struct L : public std::vector<P> {
    L(const P &a = P(), const P &b = P()) : std::vector<P>(2) {
        begin()[0] = a;
        begin()[1] = b;
    }

    // Ax + By + C = 0
    L(ld A, ld B, ld C) {
        if (std::abs(A) < eps && std::abs(B) < eps) {
            abort();
        } else if (std::abs(A) < eps) {
            *this = L(P(0, -C / B), P(1, -C / B));
        } else if (std::abs(B) < eps) {
            *this = L(P(-C / A, 0), P(-C / A, 1));
        } else {
            *this = L(P(0, -C / B), P(-C / A, 0));
        }
    }
};

struct C {
    P p;
    ld r;
    C(const P &p = 0, ld r = 0) : p(p), r(r) {}
};