Description
Input
Output
折半搜索，用散列表记录从原点出发，用了S（状压表示）这几种边（令|S|*2-1<=n），到达(x,y)的最大面积。
#include<cstdio>
#include<cmath>
#include<algorithm>
int ps[][][],pp[],r[],n,ed[],st=,ans;
#define cal(w,x,y,a,b,s) dfs(w,x+(a),y+(b),s+x*(b)-y*(a))
const int P=;
int h[P][],ht=,ds[];
void maxs(int&a,int b){if(a<b)a=b;}
void mins(int&a,int b){if(a>b)a=b;}
void ins(int st,int x,int y,int s){
int X,w,st2=(<<n)--st;
if(ds[st2]==ht){
X=(x+<<|y+)<<|st2;
w=X%P;
while(h[w][]==ht){
if(h[w][]==X){
maxs(ans,h[w][]+s);
break;
}
if((w+=)>=P)w-=P;
}
}else{
ds[st]=ht;
X=(x+<<|y+)<<|st;
w=X%P;
while(h[w][]==ht){
if(h[w][]==X){
maxs(h[w][],s);
return;
}
if((w+=)>=P)w-=P;
}
h[w][]=ht;
h[w][]=X;
h[w][]=s;
}
}
void dfs(int w,int x,int y,int s){
if(w)ins(st,x,y,s);
if(w<)
for(int i=;i<n;++i)if(!ed[i]){
ed[i]=;
st^=<<i;
int v=r[i];
for(int j=;j<pp[v];++j){
int a=ps[v][j][],b=ps[v][j][];
cal(w+,x,y,a,b,s);
cal(w+,x,y,a,-b,s);
cal(w+,x,y,-a,b,s);
cal(w+,x,y,-a,-b,s);
cal(w+,x,y,b,a,s);
cal(w+,x,y,b,-a,s);
cal(w+,x,y,-b,a,s);
cal(w+,x,y,-b,-a,s);
}
st^=<<i;
ed[i]=;
}
}
int main(){
for(int i=;i<=;++i){
for(int j=;j*j*<=i*i;++j){
int z=sqrt(i*i-j*j)+1e-;
if(j*j+z*z==i*i)ps[i][pp[i]][]=j,ps[i][pp[i]++][]=z;
}
}
while(scanf("%d",&n)==&&n){
for(int i=;i<n;++i)scanf("%d",r+i);
ans=;
++ht;
dfs(,,,);
if(!ans)puts("-1");
else if(~ans&)printf("%d\n",ans>>);
else printf("%d.5\n",ans>>);
}
return ;
}