This documentation is automatically generated by online-judge-tools/verification-helper
#include "src/geo/primitive.hpp"
using D = double;
const D PI = acos(D(-1)), EPS = 1e-10;
int sgn(D a) { return (a < -EPS) ? -1 : (a > EPS); }
int sgn(D a, D b) { return sgn(a - b); }
struct P {
D x, y;
P(D _x = D(), D _y = D()) : x(_x), y(_y) {}
P operator+(const P& r) const { return {x + r.x, y + r.y}; }
P operator-(const P& r) const { return {x - r.x, y - r.y}; }
P operator*(const P& r) const {
return {x * r.x - y * r.y, x * r.y + y * r.x};
}
P operator*(const D& r) const { return {x * r, y * r}; }
P operator/(const D& r) const { return {x / r, y / r}; }
P& operator+=(const P& r) { return *this = *this + r; }
P& operator-=(const P& r) { return *this = *this - r; }
P& operator*=(const P& r) { return *this = *this * r; }
P& operator*=(const D& r) { return *this = *this * r; }
P& operator/=(const D& r) { return *this = *this / r; }
P operator-() const { return {-x, -y}; }
bool operator<(const P& r) const {
return 2 * sgn(x, r.x) + sgn(y, r.y) < 0;
}
bool operator==(const P& r) const { return sgn((*this - r).rabs()) == 0; }
bool operator!=(const P& r) const { return !(*this == r); }
D norm() const { return x * x + y * y; }
D abs() const { return sqrt(norm()); }
D rabs() const { return max(std::abs(x), std::abs(y)); } // robust abs
D arg() const { return atan2(y, x); }
pair<D, D> to_pair() const { return {x, y}; }
static P polar(D le, D th) { return {le * cos(th), le * sin(th)}; }
};
ostream& operator<<(ostream& os, const P& p) {
return os << "P(" << p.x << ", " << p.y << ")";
}
struct L {
P s, t;
L(P _s = P(), P _t = P()) : s(_s), t(_t) {}
P vec() const { return t - s; }
D abs() const { return vec().abs(); }
D arg() const { return vec().arg(); }
};
ostream& operator<<(ostream& os, const L& l) {
return os << "L(" << l.s << ", " << l.t << ")";
}
D crs(P a, P b) { return a.x * b.y - a.y * b.x; }
D dot(P a, P b) { return a.x * b.x + a.y * b.y; }
// cross(a, b) is too small?
int sgncrs(P a, P b) {
D cr = crs(a, b);
if (abs(cr) <= (a.rabs() + b.rabs()) * EPS) return 0;
return (cr < 0) ? -1 : 1;
}
// -2, -1, 0, 1, 2 : front, clock, on, cclock, back
int ccw(P b, P c) {
int s = sgncrs(b, c);
if (s) return s;
if (!sgn(c.rabs()) || !sgn((c - b).rabs())) return 0;
if (dot(b, c) < 0) return 2;
if (dot(-b, c - b) < 0) return -2;
return 0;
}
int ccw(P a, P b, P c) { return ccw(b - a, c - a); }
int ccw(L l, P p) { return ccw(l.s, l.t, p); }
#line 1 "src/geo/primitive.hpp"
using D = double;
const D PI = acos(D(-1)), EPS = 1e-10;
int sgn(D a) { return (a < -EPS) ? -1 : (a > EPS); }
int sgn(D a, D b) { return sgn(a - b); }
struct P {
D x, y;
P(D _x = D(), D _y = D()) : x(_x), y(_y) {}
P operator+(const P& r) const { return {x + r.x, y + r.y}; }
P operator-(const P& r) const { return {x - r.x, y - r.y}; }
P operator*(const P& r) const {
return {x * r.x - y * r.y, x * r.y + y * r.x};
}
P operator*(const D& r) const { return {x * r, y * r}; }
P operator/(const D& r) const { return {x / r, y / r}; }
P& operator+=(const P& r) { return *this = *this + r; }
P& operator-=(const P& r) { return *this = *this - r; }
P& operator*=(const P& r) { return *this = *this * r; }
P& operator*=(const D& r) { return *this = *this * r; }
P& operator/=(const D& r) { return *this = *this / r; }
P operator-() const { return {-x, -y}; }
bool operator<(const P& r) const {
return 2 * sgn(x, r.x) + sgn(y, r.y) < 0;
}
bool operator==(const P& r) const { return sgn((*this - r).rabs()) == 0; }
bool operator!=(const P& r) const { return !(*this == r); }
D norm() const { return x * x + y * y; }
D abs() const { return sqrt(norm()); }
D rabs() const { return max(std::abs(x), std::abs(y)); } // robust abs
D arg() const { return atan2(y, x); }
pair<D, D> to_pair() const { return {x, y}; }
static P polar(D le, D th) { return {le * cos(th), le * sin(th)}; }
};
ostream& operator<<(ostream& os, const P& p) {
return os << "P(" << p.x << ", " << p.y << ")";
}
struct L {
P s, t;
L(P _s = P(), P _t = P()) : s(_s), t(_t) {}
P vec() const { return t - s; }
D abs() const { return vec().abs(); }
D arg() const { return vec().arg(); }
};
ostream& operator<<(ostream& os, const L& l) {
return os << "L(" << l.s << ", " << l.t << ")";
}
D crs(P a, P b) { return a.x * b.y - a.y * b.x; }
D dot(P a, P b) { return a.x * b.x + a.y * b.y; }
// cross(a, b) is too small?
int sgncrs(P a, P b) {
D cr = crs(a, b);
if (abs(cr) <= (a.rabs() + b.rabs()) * EPS) return 0;
return (cr < 0) ? -1 : 1;
}
// -2, -1, 0, 1, 2 : front, clock, on, cclock, back
int ccw(P b, P c) {
int s = sgncrs(b, c);
if (s) return s;
if (!sgn(c.rabs()) || !sgn((c - b).rabs())) return 0;
if (dot(b, c) < 0) return 2;
if (dot(-b, c - b) < 0) return -2;
return 0;
}
int ccw(P a, P b, P c) { return ccw(b - a, c - a); }
int ccw(L l, P p) { return ccw(l.s, l.t, p); }