Computational Geometry: Points, Lines, and Convex Hull

cross(AB, AC) = (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x)

def cross(O, A, B):
    return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])

def dot(A, B):
    return A[0]*B[0] + A[1]*B[1]

def dist2(A, B):  # squared distance (integer, avoids float)
    return (A[0]-B[0])**2 + (A[1]-B[1])**2

# Check if point P is on segment AB
def on_segment(A, B, P):
    if cross(A, B, P) != 0: return False
    return (min(A[0],B[0]) <= P[0] <= max(A[0],B[0]) and
            min(A[1],B[1]) <= P[1] <= max(A[1],B[1]))

# Check if segments AB and CD intersect
def segments_intersect(A, B, C, D):
    d1 = cross(C, D, A)
    d2 = cross(C, D, B)
    d3 = cross(A, B, C)
    d4 = cross(A, B, D)
    if ((d1>0 and d2<0) or (d1<0 and d2>0)) and        ((d3>0 and d4<0) or (d3<0 and d4>0)):
        return True
    if d1==0 and on_segment(C, D, A): return True
    if d2==0 and on_segment(C, D, B): return True
    if d3==0 and on_segment(A, B, C): return True
    if d4==0 and on_segment(A, B, D): return True
    return False

# Convex Hull: Graham Scan O(n log n)
def convex_hull(points):
    points = sorted(set(points))
    if len(points) <= 1: return points
    def build(pts):
        hull = []
        for p in pts:
            while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
                hull.pop()
            hull.append(p)
        return hull
    return build(points) + build(points[::-1])[1:-1]

# Area of polygon (Shoelace formula)
def polygon_area(pts):
    n = len(pts)
    area = 0
    for i in range(n):
        j = (i + 1) % n
        area += pts[i][0] * pts[j][1]
        area -= pts[j][0] * pts[i][1]
    return abs(area) / 2

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

typedef long long ll;
typedef pair<ll,ll> Point;

ll cross(Point O, Point A, Point B) {
    return (A.first-O.first)*(B.second-O.second) -
           (A.second-O.second)*(B.first-O.first);
}

vector<Point> convexHull(vector<Point> pts) {
    int n = pts.size();
    if (n < 3) return pts;
    sort(pts.begin(), pts.end());
    vector<Point> hull;
    // Lower hull
    for (auto& p : pts) {
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), p) <= 0)
            hull.pop_back();
        hull.push_back(p);
    }
    // Upper hull
    int lower_size = hull.size();
    for (int i = n-2; i >= 0; i--) {
        while ((int)hull.size() > lower_size &&
               cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    hull.pop_back();
    return hull;
}