Biorąc pod uwagę listę współrzędnych całkowitych, znajdź obszar największego wypukłego wielokąta, jaki możesz zbudować z listy, tak aby -

• każdy wierzchołek jest na liście
• żaden element listy nie jest zawarty w wielokącie.

Przykład:

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

Wizualizowane:

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

Największy wypukły wielokąt, jaki możesz z tego zrobić, to:

o     
o  o  
 o   o
  o  o
   o
     o

O powierzchni 12.

Możesz wziąć listę współrzędnych w dowolnym rozsądnym formacie i powinieneś wypisać (w odpowiedni sposób dla swojego wybranego języka) obszar największego wypukłego wielokąta, zaokrąglony do co najmniej 2 cyfr po przecinku.

Dodatkowo musisz zastosować jakiś algorytm, a nie po prostu brutalną siłę wszystkich podzbiorów punktów. Aby to wymusić, Twój program musi rozwiązać listę 50 wierzchołków w niecałą minutę na nowoczesnym komputerze.

Najkrótszy kod w bajtach wygrywa.

JavaScript ES6, 738 bajtów

((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')

Oto wersja ES5 lub starsza, która powinna działać w większości przeglądarek i węzłów bez podkręcania: 827 bajtów

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 '))

Kod zwraca anonimową funkcję. Jako parametr wymaga tablicy punktów, takich jak [[0,1],[2,3],[4,5]]. Aby go użyć, możesz umieścić var f=go przed nim, lub jeśli chcesz go użyć z wiersza poleceń, dodaj (process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(',')))na końcu i wywołaj jaknode convpol.js '(1,2)(3,4)(5,6)'

Dzięki za wyzwanie! Ponieważ nie ma implementacji referencyjnej, nie mogę udowodnić, że jest to poprawne, ale jest spójne przynajmniej w przypadku permutacji listy punktów. Prawie nie myślałem, że to zadziała, ponieważ wersje z kodem debugowania, nawet wyłączone, były zbyt wolne z wykładniczym wzrostem czasu. Mimo to zdecydowałem się na grę w golfa i cieszyłem się, że spadłem do mniej niż 2 sekund na 50 punktów na moim komputerze. Może obliczyć około 130 punktów w ciągu 1 minuty.

Algorytm jest podobny do skanu Grahama , z tym wyjątkiem, że musi szukać wszędzie pustych wypukłych kadłubów.

Wyjaśnienie

Oto ogólny przegląd działania algorytmu. Istotą tego algorytmu jest po prostu wyszukiwanie wypukłych pętli przeciwnie do ruchu wskazówek zegara, które nie zawierają punktu. Procedura jest mniej więcej taka:

1. Zacznij od pary punktów i listy wszystkich innych punktów.
2. Jeśli bieżąca para punktów przechodzi dokładnie przez dowolny punkt na liście, zatrzymaj się.
3. Odfiltruj wszystkie punkty zgodnie z ruchem wskazówek zegara od bieżącej pary, ponieważ utworzą one wklęsły wielokąt.
4. Dla wszystkich pozostałych punktów wykonaj następujące czynności:
   1. Jeśli linia od tego punktu do pierwszego punktu łańcucha przechodzi lub otacza jakiekolwiek punkty przeciwnie do ruchu wskazówek zegara, pomiń ten punkt, ponieważ wszystkie wielokąty otaczają ten punkt.
   2. Dodaj ten punkt do łańcucha, powtórz od kroku 1 z bieżącym łańcuchem i listą punktów.
5. Jeśli nie pozostały żadne punkty, a łańcuch ma co najmniej 3 punkty, jest to prawidłowy wielokąt wypukły. Pamiętaj o największym obszarze tych wielokątów.

Ponadto, jako optymalizacja, zapisujemy początkową parę łańcucha jako sprawdzoną, więc wszelkie wyszukiwania po zobaczeniu tej pary w dowolnym miejscu w łańcuchu mogą natychmiast przerwać wyszukiwanie, ponieważ największy wielokąt z tą parą został już znaleziony.

Ten algorytm nigdy nie powinien znaleźć wielokąta dwa razy i eksperymentalnie to zweryfikowałem.