G3 Konvexní obal

var datasets = [
  {arg: [[0,0], [1, 0], [1, 1], [0,1]], out: [[0,0], [1, 0], [1, 1], [0,1]]},
  {arg: [[0,0], [0,1], [0.5, 0.5], [1, 0], [1, 1]], out: [[0,0], [1, 0], [1, 1], [0,1]]},
  {arg: [[0,0], [0.5, 0.5], [0.5,1], [1, 0]], out: [[0,0], [1, 0], [0.5, 1]]},
  {arg: [[0.2, 9.9], [0.5, 8.7], [1.0, 10.0], [3.6, 9.7], [4.1, 5.7], [5.0, 5.4], [5.6, 3.3], [6.0, 0.4], [7.6, 9.4], [8.1, 0.6]], out:[[0.2, 9.9], [0.5, 8.7], [6, 0.4], [8.1, 0.6], [7.6, 9.4], [1, 10]]},
  {arg: [[1.7, 9.8], [2.9, 9.4], [3.4, 2.6], [3.4, 4.4], [4.2, 4.9], [4.9, 3.1], [4.9, 7.4], [6.2, 6.5], [6.7, 2.0], [6.8, 2.0], [8.0, 8.6], [8.8, 3.3], [9.5, 3.7]], out:[[1.7, 9.8], [3.4, 2.6], [6.7, 2], [6.8, 2], [9.5, 3.7], [8, 8.6]]},
  {arg: [[7.4, 5.2], [6.2, 7.0], [4.9, 6.3], [4.9, 3.2], [5.3, 6.0], [6.9, 9.4], [7.5, 7.3], [3.2, 4.7], [5.4, 1.6], [4.5, 4.9], [8.0, 4.5], [1.4, 4.2], [5.1, 3.1]], out: [[7.4, 5.2], [4.5, 4.9], [3.2, 4.7], [1.4, 4.2], [5.4, 1.6], [8.0, 4.5], [7.5, 7.3], [6.9, 9.4], [4.9, 6.3], [5.3, 6.0]]}
]

var names = ['body'];
const req = (a, b) => Math.round(a*1000) === Math.round(b*1000);
var validator = (result, {out}) => (out.length == result.length) && out.every((p, i) => req(p[0], result[i][0]) && req(p[1], result[i][1]))
var remapInput = `_main_inputs = [list(p) for p in _main_inputs]`

Program dostává seznam bodů v rovině. Vždycky jsou alespoň tři.

Jako výsledek vrací nejmenší konvexní mnohoúhelník, který obsahuje všechny zadané body.

• Slovo nejmenší je tam proto, že by stačilo udělat velký čtverec okolo, a to nechceme. Jinými slovy, mnohoúhelník smíme sestavit jen z bodů, které jsme dostali na vstupu.
• Slovo konvexní je tam proto, že by možná stačilo body nahodile pospojovat čarou, a to nechceme. Mnohoúhelník, který vyrobíme, nesmí mít na okraji žádná vydutá místa. Stručně řečeno, vypadá to, jako bychom zadané body zabalili do pružné folie.

Mnohoúhelník na výstupu má být vyjmenovaný proti směru hodinových ručiček. Aby vám kód prošel testy tady na webu, musí první bod být ten nejvíc nalevo.

Kdyby vám to nevycházelo, pošlete mi aspoň nefuknční kód a vysvětlení.

Smíte používat modul numpy, ale možná vám tady bude spíš na obtíž.

Rady

Jeden postup, jak vyrobit konvexní obal, staví na tom, že body nejdřív seřadíme proti směru hodinových ručiček. Abych vám usnadnil práci, tak to už je hotové, a jen to tady popíšu podrobně:

1. Vybereme si bod nejvíc nalevo jako střed. Tím, že je nejvíc nalevo, máme záruku, že to bude první bod na výstupu.
2. Napíšeme funkci, která oproti tomu středu určuje úhel k libovolnému bodu. V principu to bude math.atan2(y, x), jen musíme odečíst ten střed a dát pozor, že body máme zapsané jako (x, y).
3. Poprosíme list.sort, aby seřadil body na základě úhlu.

Z toho už nám vzniká mnohoúhelník, jen je někdy chlupatý (slušně řečeno, nekonvexní). Potřebujeme z něj vymazat všechna vydutá místa.

1. Vytvoříme si seznam vysledek, který na začátku je prázdný.
2. Projdeme cyklem každý bod (tak, jak jsme je seřadili) a:
   • Pokud ve výsledku je jen jeden bod nebo není žádný, nemusíme nic řešit.
   • Jinak se podíváme na směr poslední úsečky a směr úsečky, kterou bychom teď vytvořili. Jestli ten úhel je konvexní, je všechno v pořádku a můžeme pokračovat.
   • Jinak smažeme poslední bod z výsledku a vrátíme se na předchozí krok.
   • Nový bod přidáme na konec výsledku.
3. Máme hotovo.

import math

def main(body):
  stred = min(body)
  def azimut(p):
    return math.atan2(p[0] - stred[0], stred[1] - p[1]) % (2 * math.pi)

  body.sort(key=azimut)
  return body