Diberikan daftar koordinat bilangan bulat, temukan area poligon cembung terbesar yang dapat Anda buat dari daftar sedemikian rupa sehingga -

• setiap titik ada di daftar
• tidak ada elemen daftar yang terkandung dalam poligon.

Contoh:

(0, 0) (8, 0) (0, 1) (3, 1) (7, 1) (1, 2) (5, 2) (9, 2) (2, 3) (2, 3) (5, 3) (7, 3) (3, 4) (5, 5) (11, 5)

Divisualisasikan:

o       o
o  o   o
 o   o   o
  o  o o
   o
     o     o

Poligon cembung terbesar yang dapat Anda buat dari ini adalah ini:

o     
o  o  
 o   o
  o  o
   o
     o

Dengan luas 12.

Anda dapat mengambil daftar koordinat dalam format yang masuk akal, dan harus menampilkan (dengan cara yang sesuai untuk bahasa pilihan Anda) bidang poligon cembung terbesar, dibulatkan menjadi tidak kurang dari 2 digit setelah titik desimal.

Selain itu, Anda harus menggunakan semacam algoritma, dan tidak hanya memaksa semua subset poin. Untuk menegakkan ini, program Anda harus menyelesaikan daftar 50 simpul dalam waktu kurang dari satu menit pada PC modern.

Kode terpendek dalam byte menang.

Javascript ES6, 738 byte

((V,C,L,r,k,n,A,G,F,e,i,j,q)=>p=>{p=p.map((p,i)=>({i:i,x:p[0],y:p[1]}));A=(f,p,a,b,v,i)=>{for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))return 1};G=(p,i,a)=>{for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=(p,s,l,f,a,b,v)=>(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A((a,b)=>C(a,b)?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b),p,a,b)?0:(p=(v=V(a,b),p[k](x=>C(v,V(a,x))>=0)),A((a,b)=>C(a,b)>0,p,b,f)?0:(p.map(q=>F(p[k](r=>q!==r),[...s,q])),s[2]&&!p[n]&&!e[b.i][f.i]?G(s):0)));e=p.map(x=>p.map(y=>x===y));for(i=p[n];i--;){for(j=i;j--;){q=p[k]((p,x)=>x-i&&x-j);F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)})((a,b)=>({x:b.x-a.x,y:b.y-a.y}),(a,b)=>a.x*b.y-a.y*b.x,v=>v.x*v.x+v.y*v.y,0,'filter','length')

Berikut adalah versi ES5 atau kurang yang seharusnya berfungsi di sebagian besar peramban dan simpul tanpa mengubah: 827 byte

eval("(%V,C,L,r,k,n,A,G,F,e,i,j,q){@%p){p=p.map(%p,i){@{i:i,x:p[0],y:p[1]}});A=%f,p,a,b,v,i){for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))@1};G=%p,i,a){for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=%p,s,l,f,a,b,v){@(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A(%a,b){@C(a,b)!=0?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b)},p,a,b)?0:(p=(v=V(a,b),p[k](%x){@C(v,V(a,x))>=0})),A(%a,b){@C(a,b)>0},p,b,f)?0:(p.forEach(%q){@F(p[k](%r){@q!==r}),s.concat([q]))}),s[2]&&p[n]==0&&!e[b.i][f.i]?G(s):0)))};e=p.map(%x,i){@p.map(%y,j){@i==j})});for(i=p[n];i--;){for(j=i;j--;){q=p[k](%p,x){@x!=i&&x!=j});F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)}})(%a,b){@{x:b.x-a.x,y:b.y-a.y}},%a,b){@a.x*b.y-a.y*b.x},%v){@v.x*v.x+v.y*v.y},0,'filter','length')".replace(/%/g,'function(').replace(/@/g,'return '))

Kode mengembalikan fungsi anonim. Sebagai parameter, dibutuhkan array poin, seperti [[0,1],[2,3],[4,5]]. Untuk menggunakannya, Anda dapat meletakkannya di var f=depan, atau jika Anda ingin menggunakannya dari baris perintah, tambahkan (process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(',')))sampai akhir, dan panggil sepertinode convpol.js '(1,2)(3,4)(5,6)'

Terima kasih atas tantangannya! Karena tidak ada implementasi referensi, saya tidak dapat membuktikan ini benar, tetapi konsisten setidaknya untuk permutasi dari daftar poin. Saya hampir tidak berpikir ini akan berhasil, karena versi dengan kode debugging, bahkan dinonaktifkan, terlalu lambat dengan peningkatan waktu yang eksponensial. Saya memutuskan untuk golf itu, dan senang melihat bahwa itu turun menjadi di bawah 2 detik untuk 50 poin pada mesin saya. Itu dapat menghitung sekitar 130 poin dalam 1 menit.

Algoritma ini mirip dengan pemindaian Graham , kecuali bahwa ia harus mencari lambung cembung kosong di mana-mana.

Penjelasan

Berikut ini ikhtisar tingkat tinggi tentang cara kerja algoritme. Daging dari algoritma ini hanya mencari loop cembung berlawanan arah jarum jam yang tidak menyertakan titik. Prosedurnya kira-kira seperti ini:

1. Mulailah dengan sepasang poin, dan daftar semua poin lainnya.
2. Jika pasangan poin saat ini melewati titik mana pun dalam daftar, berhenti.
3. Saring semua titik searah jarum jam dari pasangan saat ini, karena mereka akan membuat cekung poligon.
4. Untuk semua poin yang tersisa, lakukan hal berikut:
   1. Jika garis dari titik ini ke titik pertama rantai melewati atau menutup titik berlawanan arah jarum jam, lewati titik ini, karena setiap poligon akan menutup titik.
   2. Tambahkan titik ini ke rantai, berulang dari langkah 1 dengan rantai saat ini dan daftar poin.
5. Jika tidak ada poin yang tersisa, dan rantai memiliki setidaknya 3 poin, ini adalah poligon cembung yang valid. Ingat area terbesar poligon ini.

Juga, sebagai pengoptimalan, kami merekam pasangan awal rantai sebagai dicentang, sehingga setiap pencarian setelah melihat pasangan ini di mana saja dalam rantai dapat segera berhenti mencari, karena poligon terbesar dengan pasangan ini telah ditemukan.

Algoritma ini seharusnya tidak pernah menemukan poligon dua kali, dan saya telah secara eksperimental memverifikasi ini.