2299. Do Two Convex Polygons Overlap

Two CONVEX polygons are given, each by its vertices in anticlockwise order with no three vertices on one line. Print YES if they share at least one point and NO otherwise. Touching counts as sharing: two polygons that meet only at a single corner, or only along part of an edge, are YES.

(0,0)(4,0)(4,4)(0,4) and (2,2)(6,2)(6,6)(2,6) -> YES overlapping (0,0)(4,0)(4,4)(0,4) and (4,0)(8,0)(8,4)(4,4) -> YES sharing an edge (0,0)(4,0)(4,4)(0,4) and (4,4)(8,4)(8,8)(4,8) -> YES sharing one corner (0,0)(4,0)(4,4)(0,4) and (5,0)(9,0)(9,4)(5,4) -> NO one unit apart

## What most people try first

Testing whether any vertex of one lies inside the other. That misses the case where neither polygon has a vertex inside the other and they still overlap: two long thin rectangles crossing in a plus sign have every vertex outside the other shape, and they certainly share a region.

Patching it by also testing every pair of edges for intersection does work, and it costs O(n * m) edge pairs. It is a perfectly good answer and it is used as the independent check for this problem's declared outputs. The reason to want something else is that it tells you nothing about WHY two shapes miss, and the method below does.

The third attempt, comparing bounding boxes, is a filter and not an answer: two diagonal strips can have identical boxes and never touch.

## A separating line, and where to look for one

Two convex sets that do not meet can be separated by a straight line. That is the fact the whole method rests on, and it has a sharper form for polygons: if such a line exists, one can be found PARALLEL TO AN EDGE of one of the two polygons. Sliding and rotating any separating line until it touches both shapes leaves it flush against an edge.

So there are only n + m directions to test. For each edge, take the direction perpendicular to it, project every vertex of both polygons onto that direction, and see whether the two resulting spans are apart.

A projection onto a direction (dx, dy) is the dot product dx * px + dy * py, an integer. No length and no normalisation is needed, because the only question asked of the projection is whether one span lies entirely to one side of the other, and scaling a direction scales both spans equally.

## The test, with touching counted as meeting

For an edge from u to v, a perpendicular direction is

(nx, ny) = (vy - uy, -(vx - ux))

Project both polygons and compare:

separated <-> max(proj A) < min(proj B) or max(proj B) < min(proj A)

Strict <, because the polygons are CLOSED regions. If the two spans merely touch, max(proj A) == min(proj B), the shapes touch too, and the statement says that is YES. Using <= here would answer NO for two squares sharing an edge, which is the second worked example and a declared test.

If any of the n + m directions separates, the answer is NO. If none does, the answer is YES.

## Cost

O((n + m)^2): for each of n + m candidate directions, project n + m vertices. At n = m = 1000 that is 4 * 10^6 dot products, which is the intended cost. A sweep over the two vertex lists in angular order brings this to O(n + m), which is worth knowing and is not needed here.

## Width

The components of the perpendicular direction are coordinate differences, so at most 2 * 10^6. A projection is that times a coordinate plus the same again, so at most 4 * 10^12 in magnitude. A signed 32-bit integer stops at 2147483647, so a 32-bit projection wraps and two spans that are far apart can come out interleaved, flipping the answer. 4 * 10^12 is below 2^53 = 9007199254740992, so a JavaScript Number is exact and no BigInt is needed.

Constraints - `3 <= n, m <= 1000` - `-1000000 <= x, y <= 1000000` - each polygon is convex, listed anticlockwise, with no three vertices on one line - touching at a single point or along part of an edge counts as sharing a point