geometry template

int dblcmp(double d) // Compare double to epsilon for zero checking
{
    if (fabs(d) < eps) return 0;
    return d > eps ? 1 : -1;
}

inline double sqr(double x) // Square of a number
{
    return x * x;
}

struct point
{
    double x, y;
    point() {} // Default constructor
    point(double _x, double _y) : x(_x), y(_y) {} // Parameterized constructor

    bool operator==(point a) const // Check if points are equal
    {
        return dblcmp(a.x - x) == 0 && dblcmp(a.y - y) == 0;
    }

    bool operator<(point a) const // Compare points lexicographically
    {
        return dblcmp(a.x - x) == 0 ? dblcmp(y - a.y) < 0 : x < a.x;
    }

    double len() // Length of the vector from origin
    {
        return hypot(x, y);
    }

    double len2() // Square of length from origin
    {
        return x * x + y * y;
    }

    double distance(point p) // Distance between two points
    {
        return hypot(x - p.x, y - p.y);
    }

    point add(point p) // Vector addition of two points
    {
        return point(x + p.x, y + p.y);
    }

    point sub(point p) // Vector subtraction of two points
    {
        return point(x - p.x, y - p.y);
    }

    point mul(double b) // Scalar multiplication
    {
        return point(x * b, y * b);
    }

    point div(double b) // Scalar division
    {
        return point(x / b, y / b);
    }

    double dot(point p) // Dot product
    {
        return x * p.x + y * p.y;
    }

    double det(point p) // Determinant (cross product magnitude)
    {
        return x * p.y - y * p.x;
    }

    double rad(point a, point b) // Angle between vectors (a, this), (b, this)
    {
        point p = *this;
        return fabs(atan2(fabs(a.sub(p).det(b.sub(p))), a.sub(p).dot(b.sub(p))));
    }

    point trunc(double r) // Truncate vector to length r
    {
        double l = len();
        if (!dblcmp(l)) return *this;
        r /= l;
        return point(x * r, y * r);
    }

    point rotleft() // Rotate 90 degrees counterclockwise
    {
        return point(-y, x);
    }

    point rotright() // Rotate 90 degrees clockwise
    {
        return point(y, -x);
    }

    point rotate(point p, double angle) // Rotate around point p by angle
    {
        point v = this->sub(p);
        double c = cos(angle), s = sin(angle);
        return point(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
    }
};

struct line
{
    point a, b;

    line(point _a, point _b) : a(_a), b(_b) {} // Line from two points

    bool operator==(line v) // Check if two lines are equal
    {
        return (a == v.a) && (b == v.b);
    }

    double length() // Length of the line segment
    {
        return a.distance(b);
    }

    double angle() // Angle of the line in radians
    {
        double k = atan2(b.y - a.y, b.x - a.x);
        if (dblcmp(k) < 0) k += pi;
        if (dblcmp(k - pi) == 0) k -= pi;
        return k;
    }

    int relation(point p) // Relation of point to line (clockwise, counterclockwise, collinear)
    {
        int c = dblcmp(p.sub(a).det(b.sub(a)));
        if (c < 0) return 1;
        if (c > 0) return 2;
        return 3;
    }

    bool pointonseg(point p) // Check if point is on segment
    {
        return dblcmp(p.sub(a).det(b.sub(a))) == 0 && dblcmp(p.sub(a).dot(p.sub(b))) <= 0;
    }

    bool parallel(line v) // Check if two lines are parallel
    {
        return dblcmp(b.sub(a).det(v.b.sub(v.a))) == 0;
    }

    int segcrossseg(line v) // Check if segments cross
    {
        int d1 = dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2 = dblcmp(b.sub(a).det(v.b.sub(a)));
        int d3 = dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
        int d4 = dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2;
        return (d1 == 0 && dblcmp(v.a.sub(a).dot(v.a.sub(b))) <= 0 ||
                d2 == 0 && dblcmp(v.b.sub(a).dot(v.b.sub(b))) <= 0 ||
                d3 == 0 && dblcmp(a.sub(v.a).dot(a.sub(v.b))) <= 0 ||
                d4 == 0 && dblcmp(b.sub(v.a).dot(b.sub(v.b))) <= 0);
    }

    int linecrossseg(line v) // Check if segment crosses line
    {
        int d1 = dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2 = dblcmp(b.sub(a).det(v.b.sub(a)));
        if ((d1 ^ d2) == -2) return 2;
        return (d1 == 0 || d2 == 0);
    }

    point crosspoint(line v) // Intersection point of two lines
    {
        double a1 = v.b.sub(v.a).det(a.sub(v.a));
        double a2 = v.b.sub(v.a).det(b.sub(v.a));
        return point((a.x * a2 - b.x * a1) / (a2 - a1), (a.y * a2 - b.y * a1) / (a2 - a1));
    }

    double dispointtoline(point p) // Distance from point to line
    {
        return fabs(p.sub(a).det(b.sub(a))) / length();
    }

    double dispointtoseg(point p) // Distance from point to segment
    {
        if (dblcmp(p.sub(b).dot(a.sub(b))) < 0 || dblcmp(p.sub(a).dot(b.sub(a))) < 0)
        {
            return min(p.distance(a), p.distance(b));
        }
        return dispointtoline(p);
    }

    point lineprog(point p) // Projection of point onto line
    {
        return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a)) / b.sub(a).len2()));
    }

    point symmetrypoint(point p) // Symmetry point across line
    {
        point q = lineprog(p);
        return point(2 * q.x - p.x, 2 * q.y - p.y);
    }
};