All the functions

export type Point = { x: number; y: number };
export type Circle = { x: number; y: number; r: number };
export type Rect = { x: number; y: number; w: number; h: number };
export type Line = { a: number; b: number; c: number };
export type Polygon = Point[];

// Distance between two points
export function distance(a: Point, b: Point): number {
	return Math.hypot(b.x - a.x, b.y - a.y);
}

export function distanceSquared(a: Point, b: Point): number {
	return (b.x - a.x) ** 2 + (b.y - a.y) ** 2;
}

// Midpoint
export function midpoint(a: Point, b: Point): Point {
	return { x: (a.x + b.x) / 2, y: (a.y + b.y) / 2 };
}

// Circles
export function pointInCircle(p: Point, c: Circle): boolean {
	return distanceSquared(p, c) <= c.r ** 2;
}

export function circlesCollide(a: Circle, b: Circle): boolean {
	return distanceSquared(a, b) <= (a.r + b.r) ** 2;
}

// Rectangles
export function overlap(a1: number, a2: number, b1: number, b2: number): boolean {
	return a1 <= b2 && b1 <= a2;
}

export function rectsCollide(a: Rect, b: Rect): boolean {
	return (
		overlap(a.x, a.x + a.w, b.x, b.x + b.w) &&
		overlap(a.y, a.y + a.h, b.y, b.y + b.h)
	);
}

export function clamp(value: number, min: number, max: number): number {
	return Math.max(min, Math.min(max, value));
}

export function circleRectCollide(c: Circle, rect: Rect): boolean {
	const closest = {
		x: clamp(c.x, rect.x, rect.x + rect.w),
		y: clamp(c.y, rect.y, rect.y + rect.h)
	};
	return pointInCircle(closest, c);
}

// Lines
export function lineThrough(p1: Point, p2: Point): Line {
	return { a: p2.y - p1.y, b: p1.x - p2.x, c: p2.x * p1.y - p1.x * p2.y };
}

export function side(p: Point, line: Line): number {
	return line.a * p.x + line.b * p.y + line.c;
}

export function distanceToLine(p: Point, line: Line): number {
	return Math.abs(side(p, line)) / Math.hypot(line.a, line.b);
}

export function circleLineCollide(c: Circle, line: Line): boolean {
	return side(c, line) ** 2 <= c.r ** 2 * (line.a ** 2 + line.b ** 2);
}

// Line segments
export function subtract(a: Point, b: Point): Point {
	return { x: a.x - b.x, y: a.y - b.y };
}

export function dot(u: Point, v: Point): number {
	return u.x * v.x + u.y * v.y;
}

export function closestPointOnSegment(p: Point, a: Point, b: Point): Point {
	const d = subtract(b, a);
	const lengthSquared = dot(d, d);
	if (lengthSquared === 0) return a;
	const t = clamp(dot(subtract(p, a), d) / lengthSquared, 0, 1);
	return { x: a.x + t * d.x, y: a.y + t * d.y };
}

export function circleSegmentCollide(c: Circle, a: Point, b: Point): boolean {
	return pointInCircle(closestPointOnSegment(c, a, b), c);
}

export function lineSegmentCollide(line: Line, a: Point, b: Point): boolean {
	return side(a, line) * side(b, line) <= 0;
}

export function segmentsIntersect(a: Point, b: Point, c: Point, d: Point): boolean {
	const ab = lineThrough(a, b);
	const sc = side(c, ab);
	const sd = side(d, ab);
	if (sc === 0 && sd === 0) {
		return (
			overlap(Math.min(a.x, b.x), Math.max(a.x, b.x), Math.min(c.x, d.x), Math.max(c.x, d.x)) &&
			overlap(Math.min(a.y, b.y), Math.max(a.y, b.y), Math.min(c.y, d.y), Math.max(c.y, d.y))
		);
	}
	const cd = lineThrough(c, d);
	return sc * sd <= 0 && side(a, cd) * side(b, cd) <= 0;
}

// Convex polygons
export function edges(polygon: Polygon): [Point, Point][] {
	return polygon.map((a, i) => [a, polygon[(i + 1) % polygon.length]]);
}

export function pointInConvexPolygon(p: Point, polygon: Polygon): boolean {
	const values = edges(polygon).map(([a, b]) => side(p, lineThrough(a, b)));
	return !(values.some((v) => v > 0) && values.some((v) => v < 0));
}

export function polygonLineCollide(polygon: Polygon, line: Line): boolean {
	const values = polygon.map((vertex) => side(vertex, line));
	return Math.min(...values) <= 0 && Math.max(...values) >= 0;
}

export function axes(polygon: Polygon): Point[] {
	return edges(polygon).map(([p1, p2]) => ({ x: p2.y - p1.y, y: p1.x - p2.x }));
}

export function project(polygon: Polygon, axis: Point): [number, number] {
	const values = polygon.map((vertex) => dot(vertex, axis));
	return [Math.min(...values), Math.max(...values)];
}

export function convexPolygonsCollide(a: Polygon, b: Polygon): boolean {
	for (const axis of [...axes(a), ...axes(b)]) {
		const [aMin, aMax] = project(a, axis);
		const [bMin, bMax] = project(b, axis);
		if (!overlap(aMin, aMax, bMin, bMax)) return false;
	}
	return true;
}

export function rectToPolygon(rect: Rect): Polygon {
	return [
		{ x: rect.x, y: rect.y },
		{ x: rect.x + rect.w, y: rect.y },
		{ x: rect.x + rect.w, y: rect.y + rect.h },
		{ x: rect.x, y: rect.y + rect.h }
	];
}

export function convexPolygonRectCollide(polygon: Polygon, rect: Rect): boolean {
	return convexPolygonsCollide(polygon, rectToPolygon(rect));
}

export function convexPolygonSegmentCollide(polygon: Polygon, a: Point, b: Point): boolean {
	return convexPolygonsCollide(polygon, [a, b]);
}

export function normalize(v: Point): Point {
	const length = Math.hypot(v.x, v.y);
	return { x: v.x / length, y: v.y / length };
}

export function convexPolygonCircleCollide(polygon: Polygon, c: Circle): boolean {
	const nearest = polygon.reduce((best, v) =>
		distanceSquared(v, c) < distanceSquared(best, c) ? v : best
	);
	if (distanceSquared(nearest, c) === 0) return true;
	for (const axis of [...axes(polygon), subtract(nearest, c)].map(normalize)) {
		const [min, max] = project(polygon, axis);
		const centre = dot(c, axis);
		if (!overlap(min, max, centre - c.r, centre + c.r)) return false;
	}
	return true;
}

// Concave polygons: these work on any polygon
export function pointInPolygon(p: Point, polygon: Polygon): boolean {
	let inside = false;
	for (const [a, b] of edges(polygon)) {
		if (a.y > p.y !== b.y > p.y) {
			const crossingX = a.x + ((p.y - a.y) * (b.x - a.x)) / (b.y - a.y);
			if (p.x < crossingX) inside = !inside;
		}
	}
	return inside;
}

export function polygonSegmentCollide(polygon: Polygon, a: Point, b: Point): boolean {
	return (
		edges(polygon).some(([p, q]) => segmentsIntersect(a, b, p, q)) || pointInPolygon(a, polygon)
	);
}

export function polygonCircleCollide(polygon: Polygon, c: Circle): boolean {
	return (
		edges(polygon).some(([p, q]) => circleSegmentCollide(c, p, q)) || pointInPolygon(c, polygon)
	);
}

export function polygonsCollide(a: Polygon, b: Polygon): boolean {
	const crossing = edges(a).some(([p, q]) =>
		edges(b).some(([r, s]) => segmentsIntersect(p, q, r, s))
	);
	return crossing || pointInPolygon(a[0], b) || pointInPolygon(b[0], a);
}

export function polygonRectCollide(polygon: Polygon, rect: Rect): boolean {
	return polygonsCollide(polygon, rectToPolygon(rect));
}

// Distance between two points
export function distance(a, b) {
	return Math.hypot(b.x - a.x, b.y - a.y);
}

export function distanceSquared(a, b) {
	return (b.x - a.x) ** 2 + (b.y - a.y) ** 2;
}

// Midpoint
export function midpoint(a, b) {
	return { x: (a.x + b.x) / 2, y: (a.y + b.y) / 2 };
}

// Circles
export function pointInCircle(p, c) {
	return distanceSquared(p, c) <= c.r ** 2;
}

export function circlesCollide(a, b) {
	return distanceSquared(a, b) <= (a.r + b.r) ** 2;
}

// Rectangles
export function overlap(a1, a2, b1, b2) {
	return a1 <= b2 && b1 <= a2;
}

export function rectsCollide(a, b) {
	return (
		overlap(a.x, a.x + a.w, b.x, b.x + b.w) &&
		overlap(a.y, a.y + a.h, b.y, b.y + b.h)
	);
}

export function clamp(value, min, max) {
	return Math.max(min, Math.min(max, value));
}

export function circleRectCollide(c, rect) {
	const closest = {
		x: clamp(c.x, rect.x, rect.x + rect.w),
		y: clamp(c.y, rect.y, rect.y + rect.h)
	};
	return pointInCircle(closest, c);
}

// Lines
export function lineThrough(p1, p2) {
	return { a: p2.y - p1.y, b: p1.x - p2.x, c: p2.x * p1.y - p1.x * p2.y };
}

export function side(p, line) {
	return line.a * p.x + line.b * p.y + line.c;
}

export function distanceToLine(p, line) {
	return Math.abs(side(p, line)) / Math.hypot(line.a, line.b);
}

export function circleLineCollide(c, line) {
	return side(c, line) ** 2 <= c.r ** 2 * (line.a ** 2 + line.b ** 2);
}

// Line segments
export function subtract(a, b) {
	return { x: a.x - b.x, y: a.y - b.y };
}

export function dot(u, v) {
	return u.x * v.x + u.y * v.y;
}

export function closestPointOnSegment(p, a, b) {
	const d = subtract(b, a);
	const lengthSquared = dot(d, d);
	if (lengthSquared === 0) return a;
	const t = clamp(dot(subtract(p, a), d) / lengthSquared, 0, 1);
	return { x: a.x + t * d.x, y: a.y + t * d.y };
}

export function circleSegmentCollide(c, a, b) {
	return pointInCircle(closestPointOnSegment(c, a, b), c);
}

export function lineSegmentCollide(line, a, b) {
	return side(a, line) * side(b, line) <= 0;
}

export function segmentsIntersect(a, b, c, d) {
	const ab = lineThrough(a, b);
	const sc = side(c, ab);
	const sd = side(d, ab);
	if (sc === 0 && sd === 0) {
		return (
			overlap(Math.min(a.x, b.x), Math.max(a.x, b.x), Math.min(c.x, d.x), Math.max(c.x, d.x)) &&
			overlap(Math.min(a.y, b.y), Math.max(a.y, b.y), Math.min(c.y, d.y), Math.max(c.y, d.y))
		);
	}
	const cd = lineThrough(c, d);
	return sc * sd <= 0 && side(a, cd) * side(b, cd) <= 0;
}

// Convex polygons
export function edges(polygon) {
	return polygon.map((a, i) => [a, polygon[(i + 1) % polygon.length]]);
}

export function pointInConvexPolygon(p, polygon) {
	const values = edges(polygon).map(([a, b]) => side(p, lineThrough(a, b)));
	return !(values.some((v) => v > 0) && values.some((v) => v < 0));
}

export function polygonLineCollide(polygon, line) {
	const values = polygon.map((vertex) => side(vertex, line));
	return Math.min(...values) <= 0 && Math.max(...values) >= 0;
}

export function axes(polygon) {
	return edges(polygon).map(([p1, p2]) => ({ x: p2.y - p1.y, y: p1.x - p2.x }));
}

export function project(polygon, axis) {
	const values = polygon.map((vertex) => dot(vertex, axis));
	return [Math.min(...values), Math.max(...values)];
}

export function convexPolygonsCollide(a, b) {
	for (const axis of [...axes(a), ...axes(b)]) {
		const [aMin, aMax] = project(a, axis);
		const [bMin, bMax] = project(b, axis);
		if (!overlap(aMin, aMax, bMin, bMax)) return false;
	}
	return true;
}

export function rectToPolygon(rect) {
	return [
		{ x: rect.x, y: rect.y },
		{ x: rect.x + rect.w, y: rect.y },
		{ x: rect.x + rect.w, y: rect.y + rect.h },
		{ x: rect.x, y: rect.y + rect.h }
	];
}

export function convexPolygonRectCollide(polygon, rect) {
	return convexPolygonsCollide(polygon, rectToPolygon(rect));
}

export function convexPolygonSegmentCollide(polygon, a, b) {
	return convexPolygonsCollide(polygon, [a, b]);
}

export function normalize(v) {
	const length = Math.hypot(v.x, v.y);
	return { x: v.x / length, y: v.y / length };
}

export function convexPolygonCircleCollide(polygon, c) {
	const nearest = polygon.reduce((best, v) =>
		distanceSquared(v, c) < distanceSquared(best, c) ? v : best
	);
	if (distanceSquared(nearest, c) === 0) return true;
	for (const axis of [...axes(polygon), subtract(nearest, c)].map(normalize)) {
		const [min, max] = project(polygon, axis);
		const centre = dot(c, axis);
		if (!overlap(min, max, centre - c.r, centre + c.r)) return false;
	}
	return true;
}

// Concave polygons: these work on any polygon
export function pointInPolygon(p, polygon) {
	let inside = false;
	for (const [a, b] of edges(polygon)) {
		if (a.y > p.y !== b.y > p.y) {
			const crossingX = a.x + ((p.y - a.y) * (b.x - a.x)) / (b.y - a.y);
			if (p.x < crossingX) inside = !inside;
		}
	}
	return inside;
}

export function polygonSegmentCollide(polygon, a, b) {
	return (
		edges(polygon).some(([p, q]) => segmentsIntersect(a, b, p, q)) || pointInPolygon(a, polygon)
	);
}

export function polygonCircleCollide(polygon, c) {
	return (
		edges(polygon).some(([p, q]) => circleSegmentCollide(c, p, q)) || pointInPolygon(c, polygon)
	);
}

export function polygonsCollide(a, b) {
	const crossing = edges(a).some(([p, q]) =>
		edges(b).some(([r, s]) => segmentsIntersect(p, q, r, s))
	);
	return crossing || pointInPolygon(a[0], b) || pointInPolygon(b[0], a);
}

export function polygonRectCollide(polygon, rect) {
	return polygonsCollide(polygon, rectToPolygon(rect));
}

import math
from dataclasses import dataclass


@dataclass
class Point:
    x: float
    y: float


@dataclass
class Circle:
    x: float
    y: float
    r: float


@dataclass
class Rect:
    x: float
    y: float
    w: float
    h: float


@dataclass
class Line:
    a: float
    b: float
    c: float


Polygon = list[Point]


# Distance between two points
def distance(a: Point, b: Point) -> float:
    return math.hypot(b.x - a.x, b.y - a.y)


def distance_squared(a: Point, b: Point) -> float:
    return (b.x - a.x) ** 2 + (b.y - a.y) ** 2


# Midpoint
def midpoint(a: Point, b: Point) -> Point:
    return Point((a.x + b.x) / 2, (a.y + b.y) / 2)


# Circles
def point_in_circle(p: Point, c: Circle) -> bool:
    return distance_squared(p, c) <= c.r ** 2


def circles_collide(a: Circle, b: Circle) -> bool:
    return distance_squared(a, b) <= (a.r + b.r) ** 2


# Rectangles
def overlap(a1: float, a2: float, b1: float, b2: float) -> bool:
    return a1 <= b2 and b1 <= a2


def rects_collide(a: Rect, b: Rect) -> bool:
    return (
        overlap(a.x, a.x + a.w, b.x, b.x + b.w)
        and overlap(a.y, a.y + a.h, b.y, b.y + b.h)
    )


def clamp(value: float, low: float, high: float) -> float:
    return max(low, min(high, value))


def circle_rect_collide(c: Circle, rect: Rect) -> bool:
    closest = Point(
        clamp(c.x, rect.x, rect.x + rect.w),
        clamp(c.y, rect.y, rect.y + rect.h),
    )
    return point_in_circle(closest, c)


# Lines
def line_through(p1: Point, p2: Point) -> Line:
    return Line(p2.y - p1.y, p1.x - p2.x, p2.x * p1.y - p1.x * p2.y)


def side(p: Point, line: Line) -> float:
    return line.a * p.x + line.b * p.y + line.c


def distance_to_line(p: Point, line: Line) -> float:
    return abs(side(p, line)) / math.hypot(line.a, line.b)


def circle_line_collide(c: Circle, line: Line) -> bool:
    return side(c, line) ** 2 <= c.r ** 2 * (line.a ** 2 + line.b ** 2)


# Line segments
def subtract(a: Point, b: Point) -> Point:
    return Point(a.x - b.x, a.y - b.y)


def dot(u: Point, v: Point) -> float:
    return u.x * v.x + u.y * v.y


def closest_point_on_segment(p: Point, a: Point, b: Point) -> Point:
    d = subtract(b, a)
    length_squared = dot(d, d)
    if length_squared == 0:
        return a
    t = clamp(dot(subtract(p, a), d) / length_squared, 0, 1)
    return Point(a.x + t * d.x, a.y + t * d.y)


def circle_segment_collide(c: Circle, a: Point, b: Point) -> bool:
    return point_in_circle(closest_point_on_segment(c, a, b), c)


def line_segment_collide(line: Line, a: Point, b: Point) -> bool:
    return side(a, line) * side(b, line) <= 0


def segments_intersect(a: Point, b: Point, c: Point, d: Point) -> bool:
    ab = line_through(a, b)
    sc = side(c, ab)
    sd = side(d, ab)
    if sc == 0 and sd == 0:
        return overlap(
            min(a.x, b.x), max(a.x, b.x), min(c.x, d.x), max(c.x, d.x)
        ) and overlap(min(a.y, b.y), max(a.y, b.y), min(c.y, d.y), max(c.y, d.y))
    cd = line_through(c, d)
    return sc * sd <= 0 and side(a, cd) * side(b, cd) <= 0


# Convex polygons
def edges(polygon: Polygon) -> list[tuple[Point, Point]]:
    return list(zip(polygon, polygon[1:] + polygon[:1]))


def point_in_convex_polygon(p: Point, polygon: Polygon) -> bool:
    values = [side(p, line_through(a, b)) for a, b in edges(polygon)]
    return not (any(v > 0 for v in values) and any(v < 0 for v in values))


def polygon_line_collide(polygon: Polygon, line: Line) -> bool:
    values = [side(vertex, line) for vertex in polygon]
    return min(values) <= 0 <= max(values)


def axes(polygon: Polygon) -> list[Point]:
    return [Point(p2.y - p1.y, p1.x - p2.x) for p1, p2 in edges(polygon)]


def project(polygon: Polygon, axis: Point) -> tuple[float, float]:
    values = [dot(vertex, axis) for vertex in polygon]
    return min(values), max(values)


def convex_polygons_collide(a: Polygon, b: Polygon) -> bool:
    for axis in axes(a) + axes(b):
        a_min, a_max = project(a, axis)
        b_min, b_max = project(b, axis)
        if not overlap(a_min, a_max, b_min, b_max):
            return False
    return True


def rect_to_polygon(rect: Rect) -> Polygon:
    return [
        Point(rect.x, rect.y),
        Point(rect.x + rect.w, rect.y),
        Point(rect.x + rect.w, rect.y + rect.h),
        Point(rect.x, rect.y + rect.h),
    ]


def convex_polygon_rect_collide(polygon: Polygon, rect: Rect) -> bool:
    return convex_polygons_collide(polygon, rect_to_polygon(rect))


def convex_polygon_segment_collide(polygon: Polygon, a: Point, b: Point) -> bool:
    return convex_polygons_collide(polygon, [a, b])


def normalize(v: Point) -> Point:
    length = math.hypot(v.x, v.y)
    return Point(v.x / length, v.y / length)


def convex_polygon_circle_collide(polygon: Polygon, c: Circle) -> bool:
    nearest = min(polygon, key=lambda v: distance_squared(v, c))
    if distance_squared(nearest, c) == 0:
        return True
    for axis in map(normalize, axes(polygon) + [subtract(nearest, c)]):
        low, high = project(polygon, axis)
        centre = dot(c, axis)
        if not overlap(low, high, centre - c.r, centre + c.r):
            return False
    return True


# Concave polygons: these work on any polygon
def point_in_polygon(p: Point, polygon: Polygon) -> bool:
    inside = False
    for a, b in edges(polygon):
        if (a.y > p.y) != (b.y > p.y):
            crossing_x = a.x + (p.y - a.y) * (b.x - a.x) / (b.y - a.y)
            if p.x < crossing_x:
                inside = not inside
    return inside


def polygon_segment_collide(polygon: Polygon, a: Point, b: Point) -> bool:
    return any(
        segments_intersect(a, b, p, q) for p, q in edges(polygon)
    ) or point_in_polygon(a, polygon)


def polygon_circle_collide(polygon: Polygon, c: Circle) -> bool:
    return any(
        circle_segment_collide(c, p, q) for p, q in edges(polygon)
    ) or point_in_polygon(c, polygon)


def polygons_collide(a: Polygon, b: Polygon) -> bool:
    crossing = any(
        segments_intersect(p, q, r, s) for p, q in edges(a) for r, s in edges(b)
    )
    return crossing or point_in_polygon(a[0], b) or point_in_polygon(b[0], a)


def polygon_rect_collide(polygon: Polygon, rect: Rect) -> bool:
    return polygons_collide(polygon, rect_to_polygon(rect))