Angular sweep around the centroid

// Candidate: angular sweep construction. Vertices are visited in order of their polar
// angle around the centroid (ties by radius, then index), with no local search. Tests
// whether a sweep ordering competes with nearest-neighbor construction on uniform random
// instances. Deterministic, O(n log n).
export function solve(instance) {
  const points = instance.points;
  const n = points.length;
  let cx = 0;
  let cy = 0;
  for (let i = 0; i < n; i++) {
    cx += points[i][0];
    cy += points[i][1];
  }
  cx /= n;
  cy /= n;
  const angle = new Float64Array(n);
  const radius = new Float64Array(n);
  for (let i = 0; i < n; i++) {
    const dx = points[i][0] - cx;
    const dy = points[i][1] - cy;
    angle[i] = Math.atan2(dy, dx);
    radius[i] = dx * dx + dy * dy;
  }
  const order = new Array(n);
  for (let i = 0; i < n; i++) order[i] = i;
  order.sort((a, b) => angle[a] - angle[b] || radius[a] - radius[b] || a - b);
  return order;
}