interface Point {
  x: number;
  y: number;
}

interface Vector {
  x: number;
  y: number;
}

function cross(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 pointToLineDistance(p: Point, a: Point, b: Point): number {
  const numerator = Math.abs((b.y - a.y) * p.x - (b.x - a.x) * p.y + b.x * a.y - b.y * a.x);
  const denominator = Math.sqrt((b.y - a.y) ** 2 + (b.x - a.x) ** 2);
  return numerator / denominator;
}

function isPointInPolygon(point: Point, polygon: Point[]): boolean {
  let inside = false;
  const n = polygon.length;

  for (let i = 0, j = n - 1; i < n; j = i, i += 1) {
    if (polygon[i].y > point.y !== polygon[j].y > point.y && point.x < ((polygon[j].x - polygon[i].x) * (point.y - polygon[i].y)) / (polygon[j].y - polygon[i].y) + polygon[i].x) {
      inside = !inside;
    }
  }

  return inside;
}

function polygonArea(points: Point[]): number {
  let area = 0;
  const n = points.length;

  for (let i = 0; i < n; i += 1) {
    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 convexHull(points: Point[]): Point[] {
  if (points.length <= 1) return points;

  // 找到最底部的点
  let minY = Infinity;
  let minIndex = 0;

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

  // 以最底部点为基准排序
  const p0 = points[minIndex];
  points.sort((a, b) => {
    const angleA = Math.atan2(a.y - p0.y, a.x - p0.x);
    const angleB = Math.atan2(b.y - p0.y, b.x - p0.x);
    if (angleA !== angleB) return angleA - angleB;
    return (a.x - p0.x) ** 2 + (a.y - p0.y) ** 2 - (b.x - p0.x) ** 2 - (b.y - p0.y) ** 2;
  });

  // 移除共线点
  const stack: Point[] = [];
  for (const point of points) {
    while (stack.length >= 2 && cross(stack[stack.length - 2], stack[stack.length - 1], point) <= 0) {
      stack.pop();
    }
    stack.push(point);
  }

  return stack;
}

function doIntersect(a: Point, b: Point, c: Point, d: Point): boolean {
  const d1 = cross(a, b, c);
  const d2 = cross(a, b, d);
  const d3 = cross(c, d, a);
  const d4 = cross(c, d, b);

  if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
    return true;
  }

  return false;
}