¡Eres un granjero y tu rebaño de ovejas se ha escapado! ¡Oh no!

Redondee esas ovejas construyendo cercas para contenerlas. Como agricultor con un presupuesto limitado, desea utilizar la menor cantidad de cerca posible. Sin embargo, afortunadamente para ti, no son las ovejas más inteligentes del mundo y no se molestan en moverse después de haber escapado.

Tarea

Dada una lista de coordenadas, genere la menor cantidad de segmentos de cerca necesarios para contener las ovejas.

Reglas

• Las ovejas están contenidas si no pueden alejarse (sin agujeros en la cerca).
• No es necesario que contenga todas las ovejas en un bloque de cerca; podría haber múltiples áreas cercadas independientes entre sí.
• Los segmentos de cerca están orientados en direcciones cardinales.
• Cada tupla de coordenadas representa una sola oveja.
• La entrada debe ser pares enteros positivos, x>0& y>0, pero puede formatearse adecuadamente para su idioma.
  • es decir: {{1,1},{2,1},{3,7}, .. }o[1,2],[2,1],[3,7], ..
• Los espacios vacíos dentro de un área cercada están bien.
• No puede asumir que las coordenadas se ingresan en un orden específico.

Por ejemplo, una sola oveja requiere que los 4segmentos de la cerca estén completamente contenidos.

Casos de prueba

[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

Notas

• Puede asumir que las coordenadas de entrada son válidas.
• Su algoritmo debería funcionar teóricamente para cualquier coordenada entera razonablemente grande (hasta el valor máximo admitido de su idioma).
• Las respuestas completas al programa o a la función están bien.

Este es el código de golf , por lo que la respuesta más corta en bytes gana.

JavaScript (ES6), 251 244 275 bytes

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

¿Cómo?

Usamos la función recursiva P () para crear una lista de todas las particiones posibles de la lista de entrada. Esta función es actualmente subóptima, ya que devuelve algunas particiones duplicadas, lo que sin embargo no altera el resultado final.

Para cada partición, calculamos el número de cercas requeridas para rodear a todas las ovejas en cada grupo con un rectángulo. La suma de estas cercas da el puntaje de la partición. Finalmente devolvemos el puntaje más bajo.

Casos de prueba

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 bytes

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

Pruébalo en línea!