Anda seorang petani dan kawanan domba Anda telah lolos! Oh tidak!

Kumpulkan domba-domba itu dengan membangun pagar untuk menampung mereka. Sebagai petani dengan anggaran terbatas, Anda ingin menggunakan pagar seminimal mungkin. Untungnya bagi Anda, mereka bukan domba paling pintar di dunia dan tidak repot-repot bergerak setelah melarikan diri.

Tugas

Diberikan daftar koordinat, hasilkan paling sedikit segmen pagar yang diperlukan untuk menampung domba.

Aturan

• Domba terkandung jika mereka tidak bisa berkeliaran (tidak ada lubang di pagar).
• Anda tidak harus memuat semua domba dalam satu blok pagar - mungkin ada beberapa area berpagar yang terpisah satu sama lain.
• Segmen pagar berorientasi pada arah mata angin.
• Setiap tuple koordinat mewakili satu domba.
• Masukan harus berupa bilangan bulat positif, x>0& y>0, tetapi dapat diformat dengan tepat untuk bahasa Anda.
  • yaitu: {{1,1},{2,1},{3,7}, .. }atau[1,2],[2,1],[3,7], ..
• Ruang kosong di dalam area berpagar tidak apa-apa.
• Anda tidak dapat menganggap koordinat adalah input dalam urutan tertentu.

Sebagai contoh, seekor domba tunggal membutuhkan 4segmen pagar untuk sepenuhnya terkandung.

Uji kasus

[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

Catatan

• Anda dapat menganggap koordinat input valid.
• Algoritme Anda secara teoritis harus berfungsi untuk koordinat integer yang cukup besar (hingga nilai maksimum yang didukung bahasa Anda).
• Jawaban program atau fungsi lengkap tidak masalah.

Ini kode-golf , jadi jawaban tersingkat dalam byte menang!

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

Bagaimana?

Kami menggunakan fungsi rekursif P () untuk membuat daftar semua kemungkinan partisi dari daftar input. Fungsi ini saat ini kurang optimal, karena ia mengembalikan beberapa partisi yang digandakan - yang tidak mengubah hasil akhir.

Untuk setiap partisi, kami menghitung jumlah pagar yang diperlukan untuk mengelilingi semua domba di setiap kelompok dengan persegi panjang. Jumlah pagar ini memberikan skor partisi. Kami akhirnya mengembalikan skor terendah.

Uji kasus

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 byte

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

Cobalah online!