class Point {
  constructor(
    public x: number,
    public y: number,
  ) {}

  // 向量减法
  subtract(other: Point): Point {
    return new Point(this.x - other.x, this.y - other.y);
  }

  // 向量加法
  add(other: Point): Point {
    return new Point(this.x + other.x, this.y + other.y);
  }

  // 标量乘法
  multiply(scalar: number): Point {
    return new Point(this.x * scalar, this.y * scalar);
  }

  // 叉积
  cross(other: Point): number {
    return this.x * other.y - this.y * other.x;
  }

  // 点积
  dot(other: Point): number {
    return this.x * other.x + this.y * other.y;
  }

  // 距离
  distance(other: Point): number {
    const dx = this.x - other.x;
    const dy = this.y - other.y;
    return Math.sqrt(dx * dx + dy * dy);
  }

  // 距离平方（避免开方运算）
  distanceSquared(other: Point): number {
    const dx = this.x - other.x;
    const dy = this.y - other.y;
    return dx * dx + dy * dy;
  }

  equals(other: Point): boolean {
    return this.x === other.x && this.y === other.y;
  }

  toString(): string {
    return `(${this.x}, ${this.y})`;
  }
}

class Line {
  constructor(
    public start: Point,
    public end: Point,
  ) {}

  // 线段长度
  length(): number {
    return this.start.distance(this.end);
  }

  // 方向向量
  direction(): Point {
    return this.end.subtract(this.start);
  }

  // 法向量
  normal(): Point {
    const dir = this.direction();
    return new Point(-dir.y, dir.x);
  }
}

// 计算极角
function polarAngle(p0: Point, p1: Point): number {
  const dx = p1.x - p0.x;
  const dy = p1.y - p0.y;
  return Math.atan2(dy, dx);
}

// 叉积用于判断方向
function crossProduct(o: Point, a: Point, b: Point): number {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

function grahamScan(points: Point[]): Point[] {
  if (points.length <= 1) return points;

  // 找到最底部的点
  let minY = points[0].y;
  let minIndex = 0;

  for (let i = 1; i < points.length; i++) {
    if (points[i].y < minY || (points[i].y === minY && points[i].x < points[minIndex].x)) {
      minY = points[i].y;
      minIndex = i;
    }
  }

  // 将最底部点移到数组开头
  [points[0], points[minIndex]] = [points[minIndex], points[0]];

  // 按极角排序
  const p0 = points[0];
  points.sort((a, b) => {
    const angleA = polarAngle(p0, a);
    const angleB = polarAngle(p0, b);
    if (angleA !== angleB) {
      return angleA - angleB;
    }
    // 如果极角相同，按距离排序
    return p0.distanceSquared(a) - p0.distanceSquared(b);
  });

  // 移除共线的点（除了第一个和最后一个）
  let m = 1;
  for (let i = 1; i < points.length; i++) {
    while (i < points.length - 1 && crossProduct(p0, points[i], points[i + 1]) === 0) {
      i++;
    }
    points[m] = points[i];
    m++;
  }

  if (m < 3) return points.slice(0, m);

  // Graham扫描
  const stack: Point[] = [];
  stack.push(points[0], points[1], points[2]);

  for (let i = 3; i < m; i++) {
    while (stack.length >= 2 && crossProduct(stack[stack.length - 2], stack[stack.length - 1], points[i]) <= 0) {
      stack.pop();
    }
    stack.push(points[i]);
  }

  return stack;
}

// 使用示例
function convexHullExample() {
  const points = [new Point(0, 3), new Point(1, 1), new Point(2, 2), new Point(4, 4), new Point(0, 0), new Point(1, 2), new Point(3, 1), new Point(3, 3)];

  const hull = grahamScan(points);
  console.log('凸包顶点:');
  hull.forEach((point) => console.log(point.toString()));
}

// 判断点是否在线段上
function onSegment(p: Point, q: Point, r: Point): boolean {
  return Math.min(p.x, r.x) <= q.x && q.x <= Math.max(p.x, r.x) && Math.min(p.y, r.y) <= q.y && q.y <= Math.max(p.y, r.y);
}

// 计算方向
function orientation(p: Point, q: Point, r: Point): number {
  const val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  if (Math.abs(val) < 1e-9) return 0; // 共线
  return val > 0 ? 1 : 2; // 顺时针或逆时针
}

// 检查两条线段是否相交
function doIntersect(p1: Point, q1: Point, p2: Point, q2: Point): boolean {
  const o1 = orientation(p1, q1, p2);
  const o2 = orientation(p1, q1, q2);
  const o3 = orientation(p2, q2, p1);
  const o4 = orientation(p2, q2, q1);

  // 一般情况
  if (o1 !== o2 && o3 !== o4) {
    return true;
  }

  // 特殊情况：共线且有重叠
  if (o1 === 0 && onSegment(p1, p2, q1)) return true;
  if (o2 === 0 && onSegment(p1, q2, q1)) return true;
  if (o3 === 0 && onSegment(p2, p1, q2)) return true;
  if (o4 === 0 && onSegment(p2, q1, q2)) return true;

  return false;
}

// 计算线段交点
function lineIntersection(p1: Point, q1: Point, p2: Point, q2: Point): Point | null {
  const denom = (p1.x - q1.x) * (p2.y - q2.y) - (p1.y - q1.y) * (p2.x - q2.x);

  if (Math.abs(denom) < 1e-9) {
    return null; // 平行
  }

  const t = ((p1.x - p2.x) * (p2.y - q2.y) - (p1.y - p2.y) * (p2.x - q2.x)) / denom;
  const u = -((p1.x - q1.x) * (p1.y - p2.y) - (p1.y - q1.y) * (p1.x - p2.x)) / denom;

  if (t >= 0 && t <= 1 && u >= 0 && u <= 1) {
    return new Point(p1.x + t * (q1.x - p1.x), p1.y + t * (q1.y - p1.y));
  }

  return null;
}

// 使用鞋带公式计算多边形面积
function polygonArea(points: Point[]): number {
  if (points.length < 3) return 0;

  let area = 0;
  const n = points.length;

  for (let i = 0; i < n; i++) {
    const j = (i + 1) % n;
    area += points[i].x * points[j].y;
    area -= points[j].x * points[i].y;
  }

  return Math.abs(area) / 2;
}

// 计算带符号的面积（用于判断多边形方向）
function signedPolygonArea(points: Point[]): number {
  if (points.length < 3) return 0;

  let area = 0;
  const n = points.length;

  for (let i = 0; i < n; i++) {
    const j = (i + 1) % n;
    area += points[i].x * points[j].y;
    area -= points[j].x * points[i].y;
  }

  return area / 2;
}

// 射线法判断点是否在多边形内
function pointInPolygon(point: Point, polygon: Point[]): boolean {
  let inside = false;
  const n = polygon.length;

  for (let i = 0, j = n - 1; i < n; j = i++) {
    const xi = polygon[i].x,
      yi = polygon[i].y;
    const xj = polygon[j].x,
      yj = polygon[j].y;

    if (yi > point.y !== yj > point.y && point.x < ((xj - xi) * (point.y - yi)) / (yj - yi) + xi) {
      inside = !inside;
    }
  }

  return inside;
}

// 转角法判断点是否在多边形内
function pointInPolygonWinding(point: Point, polygon: Point[]): boolean {
  let winding = 0;
  const n = polygon.length;

  for (let i = 0; i < n; i++) {
    const a = polygon[i];
    const b = polygon[(i + 1) % n];

    if (a.y <= point.y) {
      if (b.y > point.y && crossProduct(a, b, point) > 0) {
        winding++;
      }
    } else {
      if (b.y <= point.y && crossProduct(a, b, point) < 0) {
        winding--;
      }
    }
  }

  return winding !== 0;
}

// 检查多边形是否为凸多边形
function isConvex(polygon: Point[]): boolean {
  if (polygon.length < 3) return false;

  const n = polygon.length;
  let sign = 0;

  for (let i = 0; i < n; i++) {
    const a = polygon[i];
    const b = polygon[(i + 1) % n];
    const c = polygon[(i + 2) % n];

    const cross = crossProduct(a, b, c);

    if (cross !== 0) {
      if (sign === 0) {
        sign = cross > 0 ? 1 : -1;
      } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
        return false;
      }
    }
  }

  return true;
}

// 分治法求最近点对
function closestPair(points: Point[]): { distance: number; pair: [Point, Point] } {
  // 按x坐标排序
  const sortedX = points.slice().sort((a, b) => a.x - b.x);
  // 按y坐标排序
  const sortedY = points.slice().sort((a, b) => a.y - b.y);

  return closestPairUtil(sortedX, sortedY);
}

function closestPairUtil(px: Point[], py: Point[]): { distance: number; pair: [Point, Point] } {
  const n = px.length;

  if (n <= 3) {
    return bruteForce(px);
  }

  const mid = Math.floor(n / 2);
  const midPoint = px[mid];

  // 分成左右两半
  const leftX = px.slice(0, mid);
  const rightX = px.slice(mid);

  const leftY = py.filter((p) => p.x <= midPoint.x);
  const rightY = py.filter((p) => p.x > midPoint.x);

  // 递归求左右两半的最小距离
  const leftResult = closestPairUtil(leftX, leftY);
  const rightResult = closestPairUtil(rightX, rightY);

  let minResult = leftResult.distance < rightResult.distance ? leftResult : rightResult;

  // 检查跨越中线的点
  const strip: Point[] = [];
  for (const point of py) {
    if (Math.abs(point.x - midPoint.x) < minResult.distance) {
      strip.push(point);
    }
  }

  // 在strip中寻找更小的距离
  for (let i = 0; i < strip.length; i++) {
    for (let j = i + 1; j < strip.length && strip[j].y - strip[i].y < minResult.distance; j++) {
      const dist = strip[i].distance(strip[j]);
      if (dist < minResult.distance) {
        minResult = { distance: dist, pair: [strip[i], strip[j]] };
      }
    }
  }

  return minResult;
}

function bruteForce(points: Point[]): { distance: number; pair: [Point, Point] } {
  let minDist = Infinity;
  let closestPair: [Point, Point] = [points[0], points[1]];

  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      const dist = points[i].distance(points[j]);
      if (dist < minDist) {
        minDist = dist;
        closestPair = [points[i], points[j]];
      }
    }
  }

  return { distance: minDist, pair: closestPair };
}