Dada uma lista de coordenadas inteiras, encontre a área do maior polígono convexo que você pode construir a partir da lista, de modo que:

• todo vértice está na lista
• nenhum elemento da lista está contido no polígono.

Exemplo:

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

Visualizado:

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

O maior polígono convexo que você pode fazer disso é o seguinte:

o     
o  o  
 o   o
  o  o
   o
     o

Com uma área de 12.

Você pode pegar a lista de coordenadas em qualquer formato razoável e deve exibir (de maneira apropriada para o seu idioma de escolha) a área do maior polígono convexo, arredondado para não menos de 2 dígitos após o ponto decimal.

Além disso, você deve empregar algum tipo de algoritmo, e não simplesmente força bruta em todos os subconjuntos dos pontos. Para impor isso, seu programa deve resolver uma lista de 50 vértices em menos de um minuto em um PC moderno.

O menor código em bytes vence.

Javascript ES6, 738 bytes

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

Aqui está uma versão do ES5 ou menos que deve funcionar na maioria dos navegadores e nós sem ajustar: 827 bytes

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

Código retorna uma função anônima. Como parâmetro, é preciso uma matriz de pontos, como [[0,1],[2,3],[4,5]]. Para usá-lo, você pode colocá- var f=lo antes ou, se quiser usá-lo na linha de comando, adicionar (process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(',')))até o final e chamá-lo comonode convpol.js '(1,2)(3,4)(5,6)'

Obrigado pelo desafio! Como não há implementação de referência, não posso provar que isso esteja correto, mas é consistente pelo menos para permutações da lista de pontos. Eu quase não achei que isso iria funcionar, pois as versões com código de depuração, mesmo desabilitadas, eram muito lentas com o aumento exponencial do tempo. Decidi jogar golfe de qualquer maneira e fiquei satisfeito ao ver que ele caiu para menos de 2 segundos por 50 pontos na minha máquina. Pode calcular aproximadamente 130 pontos em 1 minuto.

O algoritmo é semelhante à varredura de Graham , exceto que ele precisa procurar por cascos vazios e convexos em todos os lugares.

Explicação

Aqui está uma visão geral de alto nível de como o algoritmo funciona. A essência desse algoritmo é apenas procurar loops convexos no sentido anti-horário que não incluam um ponto. O procedimento é algo como isto:

1. Comece com um par de pontos e uma lista de todos os outros pontos.
2. Se o par de pontos atual passar exatamente por qualquer ponto da lista, pare.
3. Filtre todos os pontos no sentido horário do par atual, pois eles tornariam o polígono côncavo.
4. Para todos os pontos restantes, faça o seguinte:
   1. Se uma linha desse ponto até o primeiro ponto da cadeia passar ou incluir algum ponto no sentido anti-horário, pule esse ponto, pois qualquer polígono incluiria o ponto.
   2. Adicione esse ponto à cadeia, recorra da etapa 1 com a cadeia atual e a lista de pontos.
5. Se não houver mais pontos, e a cadeia tiver pelo menos três pontos, este é um polígono convexo válido. Lembre-se da maior área desses polígonos.

Além disso, como uma otimização, registramos o par inicial da cadeia como marcado, para que qualquer pesquisa posterior ao ver esse par em qualquer lugar da cadeia possa parar imediatamente a pesquisa, uma vez que o maior polígono com esse par já foi encontrado.

Esse algoritmo nunca deve encontrar um polígono duas vezes, e eu verifiquei isso experimentalmente.