Forneça uma função para encontrar os dois pontos mais próximos entre um conjunto de pontos dados em duas dimensões. A solução direta é um algoritmo $O(n^2)$ (que podemos chamar de *algoritmo de força bruta*); o pseudo-código (usando índices) poderia ser simplesmente: <pre><strong>bruteForceClosestPair</strong> of P(1), P(2), ... P(N) <strong>if</strong> N &#x3C; 2 <strong>then</strong> <strong>return</strong> ∞ <strong>else</strong> minDistance ← |P(1) - P(2)| minPoints ← { P(1), P(2) } <strong>foreach</strong> i ∈ [1, N-1] <strong>foreach</strong> j ∈ [i+1, N] <strong>if</strong> |P(i) - P(j)| &#x3C; minDistance <strong>then</strong> minDistance ← |P(i) - P(j)| minPoints ← { P(i), P(j) } <strong>endif</strong> <strong>endfor</strong> <strong>endfor</strong> <strong>return</strong> minDistance, minPoints <strong>endif</strong> </pre> Um algoritmo melhor com base na abordagem recursiva de dividir e conquistar, com complexidade $O(n\log n)$, teria, como pseudocódigo: <pre><strong>closestPair</strong> of (xP, yP) where xP is P(1) .. P(N) sorted by x coordinate, and yP is P(1) .. P(N) sorted by y coordinate (ascending order) <strong>if</strong> N ≤ 3 <strong>then</strong> <strong>return</strong> closest points of xP using brute-force algorithm <strong>else</strong> xL ← points of xP from 1 to ⌈N/2⌉ xR ← points of xP from ⌈N/2⌉+1 to N xm ← xP(⌈N/2⌉)_x yL ← { p ∈ yP : p_x ≤ xm } yR ← { p ∈ yP : p_x > xm } (dL, pairL) ← closestPair of (xL, yL) (dR, pairR) ← closestPair of (xR, yR) (dmin, pairMin) ← (dR, pairR) <strong>if</strong> dL &#x3C; dR <strong>then</strong> (dmin, pairMin) ← (dL, pairL) <strong>endif</strong> yS ← { p ∈ yP : |xm - p_x| &#x3C; dmin } nS ← number of points in yS (closest, closestPair) ← (dmin, pairMin) <strong>for</strong> i <strong>from</strong> 1 <strong>to</strong> nS - 1 k ← i + 1 <strong>while</strong> k ≤ nS <strong>and</strong> yS(k)_y - yS(i)_y &#x3C; dmin <strong>if</strong> |yS(k) - yS(i)| &#x3C; closest <strong>then</strong> (closest, closestPair) ← (|yS(k) - yS(i)|, {yS(k), yS(i)}) <strong>endif</strong> k ← k + 1 <strong>endwhile</strong> <strong>endfor</strong> <strong>return</strong> closest, closestPair <strong>endif</strong> </pre> Para a entrada, espere que o argumento seja um array de objetos Point com membros x e y definidos como números. Retorna um objeto que contém os pares chave-valor de distance e pair (o par com os dois pontos mais próximos). Por exemplo, getClosestPair com o array de entrada points:

const points = [
  new Point(1, 2),
  new Point(3, 3),
  new Point(2, 2)
];

Retornaria:

{
  distance: 1,
  pair: [
    {
      x: 1,
      y: 2
    },
    {
      x: 2,
      y: 2
    }
  ]
}

Nota: Ordene o array pair pelos seus valores x em ordem crescente.

Testes:

• `getClosestPair` deve ser uma função.
• `getClosestPair(points1).distance` deve ser `0.0894096443343775`.
• `getClosestPair(points1).pair` deve ser `[ { x: 7.46489, y: 4.6268 }, { x: 7.46911, y: 4.71611 } ]`.
• `getClosestPair(points2).distance` deve ser `65.06919393998976`.
• `getClosestPair(points2).pair` deve ser `[ { x: 37134, y: 1963 }, { x: 37181, y: 2008 } ]`.
• `getClosestPair(points3).distance` deve ser `6754.625082119658`.
• `getClosestPair(points3).pair` deve ser `[ { x: 46817, y: 64975 }, { x: 48953, y: 58567 } ]`.