Jesteś rolnikiem, a stado owiec uciekło! O nie!

Zaokrąglij owce, budując ogrodzenia, aby je pomieścić. Jako rolnik z ograniczonym budżetem chcesz użyć jak najmniejszej ilości ogrodzenia. Na szczęście dla ciebie nie są najmądrzejszymi owcami na świecie i nie przeszkadzają w ruchu po ucieczce.

Zadanie

Biorąc pod uwagę listę współrzędnych, wypisz najmniejszą liczbę odcinków ogrodzenia koniecznych do pomieszczenia owiec.

Zasady

• Owce są zamknięte, jeśli nie mogą odejść (brak dziur w ogrodzeniu).
• Nie musisz przechowywać wszystkich owiec w jednym bloku ogrodzenia - może istnieć wiele niezależnych od siebie ogrodzonych obszarów.
• Segmenty ogrodzenia są zorientowane w głównych kierunkach.
• Każda krotka współrzędnych reprezentuje pojedynczą owcę.
• Dane wejściowe muszą być dodatnimi parami liczb całkowitych x>0i y>0, ale mogą być odpowiednio sformatowane dla twojego języka.
  • tj .: {{1,1},{2,1},{3,7}, .. }lub[1,2],[2,1],[3,7], ..
• Puste przestrzenie w ogrodzonym terenie są w porządku.
• Nie można zakładać, że współrzędne są wprowadzane w określonej kolejności.

Na przykład jedna owca wymaga 4pełnego zamknięcia segmentów ogrodzenia.

Przypadki testowe

[1,1]
4

[1,1],[1,2],[2,2]
8

[2,1],[3,1],[2,3],[1,1],[1,3],[3,2],[1,2],[3,3]
12

[1,1],[1,2],[2,2],[3,7],[4,9],[4,10],[4,11],[5,10]
22

[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9]
36

[1,1],[2,2],[3,3],[4,4],[6,6],[7,7],[8,8],[9,9]
32

[2,1],[8,3],[8,4]
10

Notatki

• Możesz założyć, że współrzędne wejściowe są prawidłowe.
• Algorytm powinien teoretycznie działać dla dowolnej rozsądnej dużej liczby całkowitej (do maksymalnej obsługiwanej wartości twojego języka).
• Odpowiedzi na pełny program lub funkcję są prawidłowe.

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach!

JavaScript (ES6), 251 244 275 bajtów

a=>Math.min(...(P=(a,r=[[a]],c=a[0])=>(a[1]&&P(a.slice(1)).map(l=>(r.push([[c],...l]),l.map((_,i)=>r.push([[c,...l[i]],...((b=[...l]).splice(i,1),b)])))),r))(a).map(L=>L.reduce((p,l)=>l.map(([h,v])=>(x=h<x?h:x,X=h<X?X:h,y=v<y?v:y,Y=v<Y?Y:v),x=y=1/0,X=Y=0)&&p+X-x+Y-y+2,0)))*2

W jaki sposób?

Używamy funkcji rekurencyjnej P (), aby utworzyć listę wszystkich możliwych partycji listy danych wejściowych. Ta funkcja jest obecnie nieoptymalna, ponieważ zwraca zduplikowane partycje - co jednak nie zmienia ostatecznego wyniku.

Dla każdej partycji obliczamy liczbę ogrodzeń wymaganych do otoczenia wszystkich owiec w każdej grupie prostokątem. Suma tych ogrodzeń daje wynik partycji. Ostatecznie zwracamy najniższy wynik.

Przypadki testowe

let f =

a=>Math.min(...(P=(a,r=[[a]],c=a[0])=>(a[1]&&P(a.slice(1)).map(l=>(r.push([[c],...l]),l.map((_,i)=>r.push([[c,...l[i]],...((b=[...l]).splice(i,1),b)])))),r))(a).map(L=>L.reduce((p,l)=>l.map(([h,v])=>(x=h<x?h:x,X=h<X?X:h,y=v<y?v:y,Y=v<Y?Y:v),x=y=1/0,X=Y=0)&&p+X-x+Y-y+2,0)))*2

console.log(f([[1,1]]))
console.log(f([[1,1],[1,2],[2,2]]))
console.log(f([[2,1],[3,1],[2,3],[1,1],[1,3],[3,2],[1,2],[3,3]]))
console.log(f([[1,1],[1,2],[2,2],[3,7],[4,9],[4,10],[4,11],[5,10]]))
console.log(f([[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9]]))
console.log(f([[1,1],[2,2],[3,3],[4,4],[6,6],[7,7],[8,8],[9,9]]))
console.log(f([[2,1],[8,3],[8,4]]))

k , 62 58 57 55 bajtów

{+//2*1+{(|/x)-&/x}'(x@?(&|/2>(|/'{x|-x}x-\:)')')/,:'x}

Wypróbuj online!