Znajdź obszar największego wypukłego wielokąta


28

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.


Czy znasz szybki algorytm w najgorszym przypadku?
xnor

3
Jeśli chcesz wymusić ograniczenie czasowe na 100 wierzchołków, prawdopodobnie powinieneś uwzględnić co najmniej jeden taki przypadek testowy (najlepiej kilka, np. Jeden, w którym wszystkie 100 wierzchołków jest częścią rozwiązania, jeden, gdzie jest 99, a jeden, gdzie jest tylko 10) .
Martin Ender,

@ MartinBüttner Niestety nie mogę wygenerować tego przypadku testowego, ponieważ sam nie mam działającej implementacji. Problem jest dość trudny :)
lub

@xnor Kilka przykładów można znaleźć tutaj .
orlp

„zaokrąglony do nie mniej niż 2 cyfr po przecinku”?
DavidC

Odpowiedzi:


12

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.


2
+1, to niesamowita odpowiedź. Możesz być w stanie zastąpić ===i !==z ==a !=, ale nie mogę być pewny, nie rozumiejąc swój kod ...
jrich

1
Dzięki! Te szczególne === i! == porównują obiekty, więc niestety niestety. Kiedyś porównywał indeksy, ale (x,i)=>p.i==i(13 znaków) jest nieco dłuższy niż x=>p===x(8 znaków) nawet po optymalizacji.
ricochet1k

2
Jest dla ciebie wyjaśnienie @Lembik
ricochet1k

1
Wygląda na to, że pobiłeś rekord O (n ^ 3) wymieniony w komentarzach do powiązanego pytania SO!

1
W porządku, dochodzę do miejsca, w którym nie wierzę, że jest możliwe, że działa to mniej niż O (n ^ 3). Jestem bardzo nowy w złożoności algorytmicznej.
ricochet1k
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.