Computational geometry problems typically operate in the real number space ℝ, requiring double-precision floating-point operations. The key challenge lies in comparing floating-point values due to precision errors. We often need to treat values like 1 and 1.0000001 as equal. We define an epsilon (ε) threshold, typically between 10⁻⁴ and 10⁻¹⁰, and implement a sign function.

const double EPS = 1e-8;
int sign(double x) { return fabs(x) <= EPS ? 0 : (x < 0 ? -1 : 1); }

This function determines the sign of a floating-point number. Based on this, we can implement various comparisons:

• x == y is equivalent to sign(x - y) == 0
• x < y is equivalent to sign(x - y) < 0
• x <= y is equivalent to sign(x - y) <= 0

We also define a square function to avoid redundant calculations:

double squared(double x) { return x * x; }

The value of π can be obtained using acos(-1):

const double PI = acos(-1);

2D Vectors

Rerpesentation

We treat vectors and points as equivalent since they have a bijection in the Cartesian coordinate system:

struct Vector2D {
    double x, y;
    Vector2D(double x = 0, double y = 0) : x(x), y(y) {}
    bool operator==(Vector2D other) { 
        return sign(x - other.x) == 0 && sign(y - other.y) == 0; 
    }
    bool operator!=(Vector2D other) { 
        return sign(x - other.x) != 0 || sign(y - other.y) != 0; 
    }
};

Linear Operations

Addition, subtraction, and scalar multiplication:

struct Vector2D {
    Vector2D operator+(Vector2D other) { 
        return Vector2D(x + other.x, y + other.y); 
    }
    Vector2D operator-(Vector2D other) { 
        return Vector2D(x - other.x, y - other.y); 
    }
    Vector2D operator-() { 
        return Vector2D(-x, -y); 
    }
    Vector2D operator*(double scalar) { 
        return Vector2D(x * scalar, y * scalar); 
    }
    Vector2D operator/(double scalar) { 
        return Vector2D(x / scalar, y / scalar); 
    }
    friend Vector2D operator*(double scalar, Vector2D vec) { 
        return Vector2D(scalar * vec.x, scalar * vec.y); 
    }
};

Magnitude and Polar Angle

The magnitude is the distance from origin: |v| = √(x² + y²). The distance between points u and v is |u-v|.

struct Vector2D {
    double magnitude() { 
        return sqrt(squared(x) + squared(y)); 
    }
    Vector2D normalized() { 
        return *this / magnitude(); 
    }
    double polarAngle() { 
        double angle = atan2(y, x); 
        return angle < 0 ? angle + 2 * PI : angle; 
    }
    Vector2D rotated(double angle) { 
        double c = cos(angle), s = sin(angle); 
        return Vector2D(c * x - s * y, s * x + c * y); 
    }
};

double distance(Vector2D a, Vector2D b) { 
    return (a - b).magnitude(); 
}
double angleBetween(Vector2D a, Vector2D b) { 
    double diff = b.polarAngle() - a.polarAngle(); 
    return diff < 0 ? diff + 2 * PI : diff; 
}

Dot Product

The dot product u·v = |u||v|cos(θ) = x_u*x_v + y_u*y_v has commutative and linear properties. Its geometric meaning is the projection of u onto v multiplied by |v|.

struct Vector2D {
    double dot(Vector2D other) { 
        return x * other.x + y * other.y; 
    }
};

bool perpendicular(Vector2D a, Vector2D b) { 
    return sign(a.dot(b)) == 0; 
}

Cross Product

In 2D, the cross product (a,b) × (x,y) = ay - bx gives the signed area of the parallelogram formed by the vectors. The sign indicates orientation:

• Positive: v is counterclockwise from u
• Zero: collinear
• Negative: v is clockwise from u

struct Vector2D {
    double cross(Vector2D other) { 
        return x * other.y - y * other.x; 
    }
};

int orientation(Vector2D a, Vector2D b) { 
    return sign(a.cross(b)); 
}

Polar Angle Sorting

To sort vectors by polar angle without using atan2 (which has precision issues), we use cross product comparisons:

struct Vector2D {
    friend bool operator<(Vector2D a, Vector2D b) {
        auto upperHalf = [](Vector2D v) { 
            return sign(v.y) > 0 || (sign(v.y) == 0 && sign(v.x) > 0); 
        };
        bool aUpper = upperHalf(a), bUpper = upperHalf(b);
        return aUpper == bUpper ? orientation(a, b) > 0 : aUpper;
    }
};

Directed Lines

Representation

A directed line is represented by a point p and a direction vector v:

struct DirectedLine {
    Vector2D origin, direction;
    DirectedLine() {}
    DirectedLine(Vector2D p, Vector2D v) : origin(p), direction(v) {}
};

Point Position Relative to Line

Determine if a point is to the left, on, or to the right of a directed line:

struct DirectedLine {
    int pointSide(Vector2D point) { 
        return orientation(direction, point - origin); 
    }
};

Parallel, Coincident, and Equal Lines

bool parallel(DirectedLine l1, DirectedLine l2) { 
    return orientation(l1.direction, l2.direction) == 0; 
}

bool coincident(DirectedLine l1, DirectedLine l2) { 
    return parallel(l1, l2) && l1.pointSide(l2.origin) == 0; 
}

bool equal(DirectedLine l1, DirectedLine l2) { 
    return l1.direction.normalized() == l2.direction.normalized() && 
           l1.pointSide(l2.origin) == 0; 
}

Line Intersection

Find intersection of two non-parallel lines:

Vector2D intersection(DirectedLine l1, DirectedLine l2) {
    Vector2D diff = l2.origin - l1.origin;
    double t = diff.cross(l2.direction) / l1.direction.cross(l2.direction);
    return l1.origin + t * l1.direction;
}

Point-to-Line Distance

struct DirectedLine {
    double distanceToPoint(Vector2D point) { 
        return fabs(direction.cross(point - origin)) / direction.magnitude(); 
    }
};

Line Segments

Representation

struct LineSegment {
    Vector2D start, end;
    LineSegment() {}
    LineSegment(Vector2D a, Vector2D b) : start(a), end(b) {}
    bool operator==(LineSegment other) { 
        return (start == other.start && end == other.end) || 
               (start == other.end && end == other.start); 
    }
};

bool parallel(LineSegment s1, LineSegment s2) {
    DirectedLine l1(s1.start, s1.end - s1.start);
    DirectedLine l2(s2.start, s2.end - s2.start);
    return parallel(l1, l2);
}

Point on Segment

struct LineSegment {
    bool contains(Vector2D point) {
        DirectedLine line(start, end - start);
        if (line.pointSide(point) != 0) return false;
        return sign(min(start.x, end.x) - point.x) <= 0 && 
               sign(point.x - max(start.x, end.x)) <= 0 &&
               sign(min(start.y, end.y) - point.y) <= 0 && 
               sign(point.y - max(start.y, end.y)) <= 0;
    }
};

Segment Intersection

bool intersect(LineSegment s1, LineSegment s2) {
    DirectedLine l1(s1.start, s1.end - s1.start);
    DirectedLine l2(s2.start, s2.end - s2.start);
    
    if (parallel(l1, l2)) {
        if (!coincident(l1, l2)) return false;
        double xOverlap = min(max(s1.start.x, s1.end.x), max(s2.start.x, s2.end.x)) - 
                         max(min(s1.start.x, s1.end.x), min(s2.start.x, s2.end.x));
        double yOverlap = min(max(s1.start.y, s1.end.y), max(s2.start.y, s2.end.y)) - 
                         max(min(s1.start.y, s1.end.y), min(s2.start.y, s2.end.y));
        return sign(xOverlap) >= 0 && sign(yOverlap) >= 0;
    } else {
        return l1.pointSide(s2.start) != l1.pointSide(s2.end) &&
               l2.pointSide(s1.start) != l2.pointSide(s1.end);
    }
}

Polygons

Representation

struct Polygon : vector<vector2d> {
    using vector<vector2d>::vector;
};
</vector2d></vector2d>

Perimeter

struct Polygon : vector<vector2d> {
    double perimeter() {
        double result = 0;
        for (size_t i = 0; i < size(); ++i) {
            result += distance((*this)[i], (*this)[(i + 1) % size()]);
        }
        return result;
    }
};
</vector2d>

Area

struct Polygon : vector<vector2d> {
    double area() {
        double result = 0;
        for (size_t i = 0; i < size(); ++i) {
            result += (*this)[i].cross((*this)[(i + 1) % size()]);
        }
        return fabs(result) / 2;
    }
};
</vector2d>

Point in Polygon

struct Polygon : vector<vector2d> {
    bool contains(Vector2D point) {
        int count = 0;
        static const Vector2D rayDir(PI, (sqrt(5) + 1) / 2);
        DirectedLine ray(point, rayDir);
        
        for (size_t i = 0; i < size(); ++i) {
            LineSegment edge((*this)[i], (*this)[(i + 1) % size()]);
            if (edge.contains(point)) return true;
            
            Vector2D intersection = ::intersection(ray, DirectedLine(edge.start, edge.end - edge.start));
            if (!LineSegment(intersection, point + rayDir).contains(point) && 
                edge.contains(intersection)) {
                ++count;
            }
        }
        return count % 2 == 1;
    }
};
</vector2d>