Geometry for OAs

Remove geometry as a source of uncertainty.

Not “learn computational geometry.” The goal is narrower and more useful: if a strong company puts an unfamiliar geometry-flavoured problem in front of you, you recognise the structure, pick the primitive, implement it correctly, and handle the degeneracies — under a clock. Everything in this file was selected against that target and nothing else.

The plan, and where the stop line is

Six sessions

How to use the file

• Concepts are open. The Toolkit tab explains everything with nothing hidden. Read it straight through.
• Problems are gated. Every approach, every recognition drill and every timed set hides its answer behind a button. Commit to an answer first, out loud or on paper, then unlock. A wrong guess you then correct is worth more than a right one you were unsure of.
• One part reading to four parts typing. This file is the one part. If you read it end to end without opening an editor you will have learned nothing, and you already know that from the 109 hards.
• Type the toolkit from memory at every session start. Two minutes. It is the difference between recognising cross and having it.

The readiness standard

You are ready when you can do all of these, not most:

Part I — what geometry actually appears

Everything below was pulled from primary sources on 16 September 2026 and every problem reference was resolved against its source before it was written down. Where the evidence is thin I say so rather than rounding it up.

Finding 1 — the frequency, company by company

Read that last row carefully. Eight of twenty-five companies — including three on your target list — have no geometry in their tag set at all. Geometry is concentrated in Google, Meta, Amazon, Microsoft, Bloomberg and Nvidia. If your pipeline is weighted towards the Indian product companies and services-adjacent shops, the honest expected value of this whole subject is lower than the effort people put into it. Week 1 is the right investment. Three weeks would not be.

Finding 2 — the 1-D projection dominates, and it is not tagged geometry

Finding 3 — the shape of the geometry that does appear

Of the 46 geometry-tagged problems, sorted by how many companies tag them, the top of the list is: 973 (10), 149 (10), 1266 (6), 223 (6), 939 (4), 2101 (4), 836 (4), 3025 (4), 3047 (4), 2481 (4). Below that, the distribution collapses — 22 of the 46 are tagged by exactly one company, and 8 by none at all.

Grouping those by what they actually require:

Finding 4 — recency

Restricting to each company's most recent six-month slice in the snapshot, geometry nearly vanishes, and what remains is concentrated: Amazon 2 (149, 973), Bloomberg 2 (973, 149), Google 3 (3464, 223, 963), Meta 1 (973), Microsoft 1 (223). Sixteen of the twenty-five companies show zero geometry in their recent slice.

Coverage matrix

Priorities below come from the evidence above, not from what a geometry textbook would emphasise.

What is deliberately excluded, and why

Before any of it: pick your number type

Geometry solutions die in the arithmetic more often than in the idea. Two minutes of this at the top of a problem buys you the rest of it.

int cross(Point a, Point b, Point c) {
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);   // int arithmetic
}

long long cross(Point a, Point b, Point c) {
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);   // STILL int arithmetic
}

struct P {
    long long x, y;                       // long long HERE — this is the fix
};

long long cross(P a, P b, P c) {          // (b-a) x (c-a)
    return (b.x - a.x) * (c.y - a.y)
         - (b.y - a.y) * (c.x - a.x);
}

Six rules that cover every OA you will see

TIER A1 · Distance, and the sqrt you must not write

Distance is the most widely tagged geometry there is, and the technique is one line. The work lies in seeing what is left once you peel the metric off.

The idea

You need to know which of two points is closer, and your hand goes to sqrt. Stop. sqrt is monotonically increasing on non-negative numbers:

So any question about the order of distances can be settled on squared distances. For integer points those are integers, making the comparison exact and epsilon-free. You need a real square root only when a length has to be printed.

long long dist2(P a, P b) {
    long long dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}

Three metrics

Separability

Manhattan distance splits into an x-part and a y-part that never interact. An L1 problem in the plane is therefore often two independent one-dimensional problems: solve each axis alone, combine at the end.

Euclidean distance offers no such split. A square root couples the axes, and coordinate-wise reasoning stops being valid the moment one shows up inside a minimisation. This is why the L1 version of a minimisation is frequently easy while the L2 version of the same sentence needs numerical methods, and why the L2 ones make poor OA questions.

Chebyshev separates too, after a change of coordinates:

// Chebyshev  ->  Manhattan
long long u = x + y, v = x - y;
// a coupled max(|dx|,|dy|) becomes two ranges you can handle independently

You will not reach for the rotation often. When you do, nothing else substitutes, and it costs four characters. The tell is a max binding |dx| to |dy|, or a region described by |x| + |y| ≤ r.

TIER A2 · The cross product

Learn this one properly. Nine of the eleven Tier A/B techniques below are built out of it.

Start from the question

Here is the situation that actually arises. You have a directed line from A to B and a third point C, and you need to know whether C lies to the left of that line, to the right of it, or exactly on it.

Triangle validity, point containment, segment crossing, polygon orientation, convexity and convex hull are all that question asked repeatedly.

Deriving it, so you never have to memorise it

Write the two vectors leaving A: u = B − A and v = C − A. The 2-D cross product of two vectors is the scalar

Two properties make it useful, and both are worth holding rather than trusting:

1. Its magnitude is the area of the parallelogram spanned by u and v, so half of it is the area of triangle ABC.
2. Its sign is positive when v is counter-clockwise from u, negative when clockwise, and zero when the two are parallel — which, for these particular vectors, means A, B and C are collinear.

Substituting u = B − A and v = C − A gives the form you write:

long long cross(P a, P b, P c) {          // sign: + left, - right, 0 collinear
    return (b.x - a.x) * (c.y - a.y)
         - (b.y - a.y) * (c.x - a.x);
}

int orient(P a, P b, P c) {               // squashed to -1 / 0 / +1
    long long v = cross(a, b, c);
    return (v > 0) - (v < 0);
}

What this one function answers

TIER A3 · Triangles

Non-degeneracy, area, containment — and the reason your Oracle problem’s own framing worked against you.

Non-degeneracy

bool isTriangle(P a, P b, P c) {
    return cross(a, b, c) != 0;          // exact: no sqrt, no epsilon, no side lengths
}

One test covers the cases the side-length form makes you enumerate by hand. Two coincident points, three identical points, and three points on a line all give cross == 0, and all get rejected.

Area

long long twiceArea(P a, P b, P c) {
    return llabs(cross(a, b, c));        // keep it doubled — stays an integer
}

Halve at the very end, and only to print. If the problem compares or maximises areas, don't halve at all — the comparisons agree either way, and you stay in exact integers.

Containment

The version below reasons about the three signs instead of assuming a counter-clockwise triangle, which is what lets it survive arbitrary input:

// returns  1 = strictly inside,  0 = on the boundary,  -1 = outside
// precondition: a, b, c is a non-degenerate triangle (check first!)
int pointInTriangle(P a, P b, P c, P p) {
    int d1 = orient(a, b, p);
    int d2 = orient(b, c, p);
    int d3 = orient(c, a, p);

    bool hasNeg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    bool hasPos = (d1 > 0) || (d2 > 0) || (d3 > 0);
    if (hasNeg && hasPos) return -1;               // signs disagree -> outside

    if (d1 == 0 || d2 == 0 || d3 == 0) return 0;   // touching an edge or vertex
    return 1;                                      // all strictly same sign
}

Your recovery for that OA

// 1. degenerate?
if (cross(A, B, C) == 0) { cout << "not a triangle"; return; }
// 2. each query point
for (P q : {P_, Q_}) {
    int r = pointInTriangle(A, B, C, q);
    cout << (r == 1 ? "inside" : r == 0 ? "on boundary" : "outside") << '\n';
}

TIER A5 · Axis-aligned rectangles

By the company data, the largest block of genuine 2-D geometry that gets asked — and the block with the least geometry inside it.

struct R { long long x1, y1, x2, y2; };   // x1<x2, y1<y2

// do they share positive AREA?  (touching edges do NOT count)
bool overlapArea(R a, R b) {
    return max(a.x1, b.x1) < min(a.x2, b.x2)
        && max(a.y1, b.y1) < min(a.y2, b.y2);
}

// do they touch or overlap?  (shared edge or corner DOES count)
bool overlapClosed(R a, R b) {
    return max(a.x1, b.x1) <= min(a.x2, b.x2)
        && max(a.y1, b.y1) <= min(a.y2, b.y2);
}

// area of the overlap (0 if none)
long long overlapAreaValue(R a, R b) {
    long long w = min(a.x2, b.x2) - max(a.x1, b.x1);
    long long h = min(a.y2, b.y2) - max(a.y1, b.y1);
    return (w > 0 && h > 0) ? w * h : 0;
}

Notice that overlapAreaValue clamps each axis separately. Multiplying two negative extents together produces a positive phantom overlap, which is the other way this gets you. Inclusion–exclusion then gives the union of two rectangles:

long long areaUnion(R a, R b) {
    long long A = (a.x2-a.x1)*(a.y2-a.y1);
    long long B = (b.x2-b.x1)*(b.y2-b.y1);
    return A + B - overlapAreaValue(a, b);
}

At three or more rectangles inclusion–exclusion needs 2ⁿ terms and you switch to a sweep, covered in §7. Recognising where that switch happens is most of the skill.

Rectangles hidden in a point set

A second and very common family hands you points and asks about rectangles they form. The geometry is trivial; the work is choosing a hash key and deciding which pairs to iterate over.

Three reusable ideas, stated without reference to any particular problem:

• Put every point in a hash set, then iterate over pairs you treat as a diagonal and look up the implied remaining corners. O(n²), and usually what the constraints intend.
• For rectangles at arbitrary angles, lean on a property that never mentions the axes — see the midpoint and length keys in §6.
• When a whole layout has to be verified, look for a pair of cheap invariants that are jointly sufficient instead of one expensive geometric check. Two weak, fast conditions often pin down a configuration that neither pins down alone, and that pattern travels well beyond geometry.

TIER A6 · Point-set hashing

Geometry that is really a hash map. What these problems test is exact integer normalisation.

Canonical slope

LC 149 · Max Points on a Line is tagged by 10 of 25 companies — LinkedIn at 56, then Apple, Citadel, Zoho, Nvidia, Meta, Google, Amazon, Bloomberg and Microsoft. Its acceptance rate is 31%, which is low for a problem whose algorithm is short and fairly obvious. The difficulty sits entirely in how you represent a slope.

// canonical direction of the line through a and b
pair<long long,long long> slopeKey(P a, P b) {
    long long dx = b.x - a.x, dy = b.y - a.y;
    long long g = std::gcd(llabs(dx), llabs(dy));
    if (g) { dx /= g; dy /= g; }
    // force one representative per direction
    if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
    return {dx, dy};
}

Read the sign-fixing line closely, because correctness lives there. After gcd reduction (2,3) and (-2,-3) describe the same line but hash differently. “If dx is negative, flip both” repairs that — except when dx == 0, where flipping on dx's sign does nothing and (0,5) and (0,-5) stay apart. Hence the second clause. Vertical lines are what people forget.

One level up: canonical line

A slope identifies a direction. To count distinct lines, or to detect parallel ones, use the implicit form Ax + By + C = 0 with A = dy, B = -dx and C = -(A·x₁ + B·y₁), then reduce the whole triple by gcd(|A|,|B|,|C|) and fix the sign the same way. CF 1163C1 · Power Transmission (Easy Edition) and its hard version drill this directly.

Grouping by exact distance

A family of shape-classification and counting questions reduces to this: compute all pairwise dist2 from an anchor, group them, count within groups. Everything stays integral, so equality is real equality rather than an approximation.

Decide whether the problem counts ordered or unordered pairs before you write k*(k-1) or k*(k-1)/2. That factor of two is a frequent wrong answer.

TIER A7 · The 1-D projection — intervals and sweep

The highest-frequency ‘geometry’ in the dataset, carrying no geometry tag. Most likely to be tested, least likely to be filed under geometry.

Why it belongs in a geometry file

Because it is geometry, collapsed. A meeting is a segment on a time line. A building in a skyline is a rectangle. A rectangle in a union-of-areas problem is an interval that stays alive over a range of y. Once you notice that a 2-D problem only ever asks about one axis at a time, it reduces to this.

// max number of simultaneously-alive intervals
int maxOverlap(vector<pair<long long,long long>> iv) {
    vector<pair<long long,int>> ev;
    for (auto [s, e] : iv) { ev.push_back({s, +1}); ev.push_back({e, -1}); }
    sort(ev.begin(), ev.end());          // ties: -1 sorts before +1, so touching does NOT overlap
    int cur = 0, best = 0;
    for (auto [x, d] : ev) { cur += d; best = max(best, cur); }
    return best;
}

The four moves

Lifting it back to 2-D

For the area of a union of many rectangles, sweep a vertical line across x. At any x the shape is a set of y-intervals, and the area between consecutive x-events is (total covered y-length) × (Δx). The new ingredient is coordinate compression: only y values appearing as rectangle edges can change the covered length, so there are at most 2n of them.

TIER B4 · Segments

Tier B: dedicated segment-intersection questions are uncommon in the company data. The degenerate cases are still the best edge-case training in the subject, and ‘do the paths cross’ is exactly the wording that produces a blank page.

Point on segment

Two conditions, both required. Collinearity puts the point somewhere on the infinite line; the bounding box clips it back to the segment.

bool onSegment(P a, P b, P p) {        // is p on segment ab (endpoints included)?
    if (cross(a, b, p) != 0) return false;                    // not even on the line
    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x)       // inside the box
        && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

Order matters here. A box test on its own admits points off the line, but a box test applied after the collinearity test cannot produce a false positive: a point both on the line and inside the box is necessarily on the segment. A zero-length segment (a == b) also works with no special case — the cross is zero for every p, and the box collapses to a single point.

Do two segments intersect?

The general case first. Segments AB and CD cross properly when C and D lie on opposite sides of line AB, and A and B lie on opposite sides of line CD. Both halves are needed — the bottom-right panel is exactly where one holds and the other does not.

bool segIntersect(P a, P b, P c, P d) {
    int d1 = orient(a, b, c), d2 = orient(a, b, d);
    int d3 = orient(c, d, a), d4 = orient(c, d, b);

    // proper crossing: strictly opposite sides, both ways
    if (d1 * d2 < 0 && d3 * d4 < 0) return true;

    // degenerate: an endpoint lies on the other segment
    if (d1 == 0 && onSegment(a, b, c)) return true;
    if (d2 == 0 && onSegment(a, b, d)) return true;
    if (d3 == 0 && onSegment(c, d, a)) return true;
    if (d4 == 0 && onSegment(c, d, b)) return true;

    return false;
}

// assumes the segments are known to intersect and are not parallel
long double t = (long double)cross(a, c, d) / cross2(b - a, d - c);
// point = a + t * (b - a)

Drills: Kattis · Line Segment Intersection forces every degenerate case, including printing a segment when the overlap is a segment. Kattis · Line Segment Distance pairs with it.

TIER B8 · Angular reasoning

The one place floating point is unavoidable. Worth learning because the ‘double the array’ trick transfers to every circular problem you will meet.

The shape of the question

You stand at a point with a field of view of θ degrees that you may aim anywhere, and you want the most you can see at once. Variants ask for the smallest angle covering everything, or the largest empty wedge. Same machine each time.

int maxInWindow(vector<P>& pts, double angleDeg, P you) {
    vector<double> a;
    int same = 0;                                   // points exactly ON you
    for (P p : pts) {
        if (p.x == you.x && p.y == you.y) { same++; continue; }   // no angle exists
        a.push_back(atan2((double)(p.y - you.y), (double)(p.x - you.x)) * 180.0 / M_PI);
    }
    sort(a.begin(), a.end());
    int n = a.size();
    for (int i = 0; i < n; i++) a.push_back(a[i] + 360.0);   // the doubling

    int best = 0;
    for (int l = 0, r = 0; r < (int)a.size(); r++) {
        while (a[r] - a[l] > angleDeg + 1e-9) l++;   // EPS: boundary counts as inside
        best = max(best, r - l + 1);
    }
    return min(best, n) + same;
}

Drill: CF 257C · View Angle inverts the objective, and makes a good second rep once you have done a first.

TIER B10 · Polygons

Shoelace is cheap. Ray casting has one genuinely nasty edge case, and meeting it here costs less than meeting it in the hidden tests.

Shoelace

long long twicePolygonArea(const vector<P>& v) {   // SIGNED: + is CCW, - is CW
    long long s = 0;
    int n = v.size();
    for (int i = 0; i < n; i++) {
        P a = v[i], b = v[(i+1) % n];
        s += a.x * b.y - a.y * b.x;                   // cross of the two position vectors
    }
    return s;                                         // abs() for area; sign for orientation
}

Two uses out of one function: llabs(s) is twice the area, and s > 0 says the vertices arrived counter-clockwise. Check that orientation before running anything that assumes a winding direction.

Point in polygon

For a convex polygon, all consecutive cross products from the query point share a sign. Simple, exact, O(n).

For a general simple polygon, cast a ray (conventionally +x) and count crossings; odd means inside. The awkward part is a ray passing exactly through a vertex, which would otherwise be counted twice or not at all.

// returns true if p is strictly inside; boundary handled separately by onSegment
bool inPolygon(const vector<P>& v, P p) {
    int n = v.size(); bool in = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        if (onSegment(v[j], v[i], p)) return true;         // boundary: decide your convention
        // the half-open y test is what makes vertices count exactly once
        bool straddles = (v[i].y > p.y) != (v[j].y > p.y);
        if (!straddles) continue;
        // x of the crossing, compared without dividing
        long long dx = v[j].x - v[i].x, dy = v[j].y - v[i].y;
        long long lhs = (p.y - v[i].y) * dx;
        long long rhs = (p.x - v[i].x) * dy;
        if (dy > 0 ? lhs > rhs : lhs < rhs) in = !in;      // flip comparison when dy is negative
    }
    return in;
}

Drills with exact feedback: Kattis · Point in Polygon and Kattis · Polygon Area.

TIER C11 · Circles

Circles appear. Circle geometry mostly does not.

Every circle-flavoured problem in the company data reduces to comparing dist2 against r². Not one needs circle–circle intersection area, tangent lines, or a circumcircle. Keep everything squared and everything stays integral.

The last row deserves a second look, because the clamp is the nearest point:

// nearest point of an axis-aligned rectangle to a point
long long cx = max(r.x1, min(c.x, r.x2));
long long cy = max(r.y1, min(c.y, r.y2));
bool hit = (c.x-cx)*(c.x-cx) + (c.y-cy)*(c.y-cy) <= rad*rad;

No case analysis, and no separate handling for a centre that lies inside the rectangle.

TIER C9 · Convex hull

Tier C, and I will be straight about why it is here at all: it appears in two problems across 25 company tag sets. It costs one evening, it is built entirely from §2, and it is the one advanced-sounding name that does turn up at Google.

vector<P> convexHull(vector<P> p, bool keepCollinear) {
    sort(p.begin(), p.end(), [](P a, P b){
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    });
    p.erase(unique(p.begin(), p.end(), [](P a, P b){
        return a.x == b.x && a.y == b.y;               // duplicates break the pop test
    }), p.end());
    if (p.size() < 3) return p;

    vector<P> h;
    for (int pass = 0; pass < 2; pass++) {              // lower, then upper
        size_t start = h.size();
        for (P q : p) {
            while (h.size() >= start + 2) {
                long long c = cross(h[h.size()-2], h[h.size()-1], q);
                if (keepCollinear ? (c < 0) : (c <= 0)) h.pop_back();
                else break;
            }
            h.push_back(q);
        }
        h.pop_back();                                   // last point starts the next pass
        reverse(p.begin(), p.end());
    }
    return h;
}

What a hull buys you

• Farthest pair. Both endpoints always lie on the hull, so you can hull first and then check pairs among far fewer points. At OA sizes the brute-force check over hull points is fine.
• Any extremal question: the point furthest in a given direction, the smallest enclosing convex shape, whether two point sets can be separated by a line.
• Convexity testing, although checking that consecutive cross products share a sign is cheaper and simpler than building a hull to compare against.

Part III — recognition

The gap you named after the Oracle OA was not knowledge. You knew the cross product. You did not connect “is this a valid triangle” to it fast enough. That connection is a trainable reflex, and this is the drill for it.

Twenty-four drills

No topic labels, deliberately mixed order. Commit to an answer before unlocking — a wrong guess that you then correct is worth more than a right guess you were not sure of, and far more than reading the answer first. Target: under ninety seconds each.

Parts V & VI — the problem set

Twenty-eight problems. Every one exists; none are invented; none carry a fabricated company attribution. Where a problem is a Codeforces or Kattis exercise rather than a reported company question, it says so in its row and explains what it trains.

Counts, and why they are what they are

Part VIII & X — timed sets and the final assessment

Real problems, realistic weight, no topic labels and no hints. The point is not whether you know the techniques — by now you do — but whether you can find them under a clock, which is the thing that actually went wrong in the De Shaw OA and in the Oracle one.

Scoring — six axes, not one

“Solved / not solved” throws away the diagnosis. Score each problem out of 2 on each axis and write the numbers down; the pattern across four sets tells you what to repair.

The standard, restated as a decision

Geometry has stopped being a variable in your OA outcome when, on Set 3 and Set 4 back to back on different days, you clear three of four inside the clock with recognition scored 2 on at least three problems per set. Anything less is not failure — it is a pointer to a section.

Part IX — how geometry solutions actually fail

Naive geometry code does not fail randomly. It fails in about a dozen specific ways, and every one of them has a two-line test case. Meeting them here is much cheaper than meeting them in the hidden tests.

The degenerate battery

Every one of these should be a test you run against your own from-memory toolkit. They are all in toolkit/selftest.cpp, which fails loudly and tells you which case broke.

Six wrong implementations, and the fix

1. The overflow that the return type does not fix

long long cross(P a, P b, P c) {          // x, y are int
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

Every operation happens in int; the widening occurs after the damage. Fix: make the members long long. Not a cast at the call site — a cast you must remember is a cast you will forget.

2. The double slope

double slope = (double)(b.y - a.y) / (b.x - a.x);
mp[slope]++;                                  // LC 149, wrong answer

auto g = std::gcd(llabs(dx), llabs(dy));
if (g) { dx /= g; dy /= g; }
if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
mp[{dx, dy}]++;                               // exact

3. The collinear blindness in segment intersection

bool segIntersect(P a, P b, P c, P d) {
    return orient(a,b,c) * orient(a,b,d) < 0
        && orient(c,d,a) * orient(c,d,b) < 0;   // misses every touching and overlapping case
}

This is right for the generic case and wrong for four of the six configurations in the diagram back in §4. The four onSegment lines are not defensive coding; they are four distinct verdicts.

4. The triangle test that assumes counter-clockwise

bool inside(P a, P b, P c, P p) {
    return orient(a,b,p) > 0 && orient(b,c,p) > 0 && orient(c,a,p) > 0;
}

Correct for a counter-clockwise triangle, silently always-false for a clockwise one. Compare the three signs to each other, as in §3, or normalise the winding first.

5. The sweep whose tie-break was never chosen

sort(ev.begin(), ev.end());   // and no comment anywhere about what happens at equal x

Not wrong, just undecided — which works on the samples and then gets flipped back the first time one seems to disagree. Write the convention in a comment when you write the sort.

6. The epsilon pointing the wrong way

while (a[r] - a[l] > angle - 1e-9) l++;    // strict where the statement was permissive

LC 1610 says a point exactly on the edge of the field of view is visible, so the tolerance must widen the window, not narrow it: > angle + 1e-9. Read the boundary sentence, then point the epsilon at it deliberately.

Stress-test the degeneracies

# find a counterexample, smallest coordinates first
python toolkit/stress.py --fast ./sol --slow ./brute --gen ./gen.py --range 3 --n 6

Part XI — the sheet you should know by heart

Everything below should be reproducible from memory in under six minutes by the end of Week 1. Type it at the start of every session until that is true. It is about sixty lines and it is the entire toolkit.

using ll = long long;

struct P {
    ll x, y;                                          // ll HERE, not int
    bool operator<(const P& o) const { return x != o.x ? x < o.x : y < o.y; }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};

ll cross(P a, P b, P c) {                             // (b-a) x (c-a)
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
int orient(P a, P b, P c) { ll v = cross(a,b,c); return (v>0) - (v<0); }

ll dot  (P a, P b, P c) { return (b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y); }
ll dist2(P a, P b)      { ll dx=a.x-b.x, dy=a.y-b.y; return dx*dx + dy*dy; }

bool onSegment(P a, P b, P p) {                       // p on segment ab, inclusive
    if (cross(a,b,p) != 0) return false;
    return min(a.x,b.x) <= p.x && p.x <= max(a.x,b.x)
        && min(a.y,b.y) <= p.y && p.y <= max(a.y,b.y);
}

bool segIntersect(P a, P b, P c, P d) {
    int d1=orient(a,b,c), d2=orient(a,b,d), d3=orient(c,d,a), d4=orient(c,d,b);
    if (d1*d2 < 0 && d3*d4 < 0) return true;
    if (d1==0 && onSegment(a,b,c)) return true;
    if (d2==0 && onSegment(a,b,d)) return true;
    if (d3==0 && onSegment(c,d,a)) return true;
    if (d4==0 && onSegment(c,d,b)) return true;
    return false;
}

int pointInTriangle(P a, P b, P c, P p) {             // 1 in, 0 boundary, -1 out
    int d1=orient(a,b,p), d2=orient(b,c,p), d3=orient(c,a,p);
    bool neg = d1<0 || d2<0 || d3<0, pos = d1>0 || d2>0 || d3>0;
    if (neg && pos) return -1;
    if (!d1 || !d2 || !d3) return 0;
    return 1;
}

ll twicePolygonArea(const vector<P>& v) {             // signed: + is CCW
    ll s = 0; int n = v.size();
    for (int i = 0; i < n; i++) {
        P a = v[i], b = v[(i+1)%n];
        s += a.x*b.y - a.y*b.x;
    }
    return s;
}

pair<ll,ll> slopeKey(P a, P b) {
    ll dx = b.x-a.x, dy = b.y-a.y, g = std::gcd(llabs(dx), llabs(dy));
    if (g) { dx /= g; dy /= g; }
    if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
    return {dx, dy};
}

struct R { ll x1, y1, x2, y2; };
bool overlapArea(R a, R b) {                          // touching does NOT count
    return max(a.x1,b.x1) < min(a.x2,b.x2) && max(a.y1,b.y1) < min(a.y2,b.y2);
}
ll overlapAreaValue(R a, R b) {
    ll w = min(a.x2,b.x2)-max(a.x1,b.x1), h = min(a.y2,b.y2)-max(a.y1,b.y1);
    return (w>0 && h>0) ? w*h : 0;
}

vector<P> convexHull(vector<P> p) {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    if (p.size() < 3) return p;
    vector<P> h;
    for (int pass = 0; pass < 2; pass++) {
        size_t st = h.size();
        for (P q : p) {
            while (h.size() >= st+2 && cross(h[h.size()-2], h[h.size()-1], q) <= 0)
                h.pop_back();                          // <= drops collinear, < keeps them
            h.push_back(q);
        }
        h.pop_back();
        reverse(p.begin(), p.end());
    }
    return h;
}

The decision table — what to reach for

Repair table — if you failed the standard