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:
- Zacznij od pary punktów i listy wszystkich innych punktów.
- Jeśli bieżąca para punktów przechodzi dokładnie przez dowolny punkt na liście, zatrzymaj się.
- Odfiltruj wszystkie punkty zgodnie z ruchem wskazówek zegara od bieżącej pary, ponieważ utworzą one wklęsły wielokąt.
- Dla wszystkich pozostałych punktów wykonaj następujące czynności:
- 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.
- Dodaj ten punkt do łańcucha, powtórz od kroku 1 z bieżącym łańcuchem i listą punktów.
- 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.