Geometry for DSA

Points and vectors, dot/cross product, orientation, line intersection, segment intersection, point-in-polygon, polygon area (shoelace), convex hull (monotonic chain and Graham scan), rotating calipers, closest pair of points, sweep line, and numerical preci…

Discuss epsilon choices, integer overflow, collinearity, duplicate points, and degenerate cases.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Use integer coordinates and exact cross products whenever possible: they avoid every epsilon question. With coordinates up to 10⁹ in absolute value, differences reach 2·10⁹ and a cross product up to 8·10¹⁸ — just inside long long (9.2·10¹⁸). The run shows that coordinates up to 2·10⁹ already overflow it; use __int128 there. With floating point, compare against a tolerance chosen from the data's scale, never with == (the run shows 0.1 + 0.2 ≠ 0.3). The monotone-chain hull uses <= 0 to drop collinear points; use < 0 to keep them. Rotating calipers walk two antipodal pointers around the hull to find its diameter in O(n); sweep line processes events sorted by x (segment intersections, rectangle union).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P { ll x, y; bool operator<(const P& o) const { return tie(x, y) < tie(o.x, o.y); } bool operator==(const P& o) const { return x == o.x && y == o.y; } };
P operator-(P a, P b) { return {a.x - b.x, a.y - b.y}; }
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }        // > 0: b is counter-clockwise from a
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }
int orient(P a, P b, P c) { ll v = cross(b - a, c - a); return (v > 0) - (v < 0); }   // 1 left turn, -1 right, 0 collinear
bool onSegment(P a, P b, P p) { return orient(a, b, p) == 0 && dot(p - a, p - b) <= 0; }
bool segmentsIntersect(P a, P b, P c, P d) {
    int o1 = orient(a, b, c), o2 = orient(a, b, d), o3 = orient(c, d, a), o4 = orient(c, d, b);
    if (o1 != o2 && o3 != o4 && o1 && o2 && o3 && o4) return true;      // proper crossing
    return onSegment(a, b, c) || onSegment(a, b, d) || onSegment(c, d, a) || onSegment(c, d, b);   // touching / collinear overlap
}
ll area2(const vector<P>& poly) { ll s = 0; for (size_t i = 0; i < poly.size(); ++i) s += cross(poly[i], poly[(i + 1) % poly.size()]); return s; }  // shoelace, twice the area
vector<P> 
…

orient((0,0),(4,0),(2,3)) = 1 (left turn)
segments (0,0)-(4,4) and (0,4)-(4,0) intersect: true; touching at an endpoint: true; parallel apart: false
convex hull (collinear and duplicate points removed): (0,0) (4,0) (4,4) (0,4)
hull area = 16
point (1,1): inside
point (3,4): outside
point (6,3): on boundary
point (7,1): outside
0.1 + 0.2 = 0.30000000000000004, equal to 0.3? false, within 1e-9? true
|cross| with coordinates up to 2e9 can reach 3.2e+19, beyond long long's 9.2e+18 - use __int128

Quiz

? What does the sign of cross(b − a, c − a) tell you?
+ Whether a → b → c turns left (positive), right (negative), or is collinear (zero) :: The basis of almost every geometry primitive.
- The distance from a to c :: No.
- The angle in degrees :: Only its sign is used.
- Whether the points are sorted :: No.

? Why prefer integer coordinates and exact cross products?
+ They are exact, so no epsilon is needed — as long as products stay in range :: 0.1 + 0.2 ≠ 0.3 in floating point.
- They are faster in every case :: Not the main reason.
- Floating point cannot represent negative numbers :: It can.
- Geometry requires integers :: Many problems use reals.

? Which degenerate cases must a segment-intersection test handle? (select all that apply)
+ Touching at an endpoint :: The run reports true.
+ Collinear overlapping segments :: onSegment checks handle them.
+ Parallel non-overlapping segments :: Must return false.
- Segments longer than 10 units :: Length is irrelevant.