今日もブログに記事を書きます Advent Calendar 2014 - Adventarやります。これは6日目です。
発想は3ステップ。
まず適当に凸多角形を書く。
v{i-1}とv{i+1}を結ぶ直線と中心からviを結ぶ直線は直行させたほうが面積が大きくなる。
ということで最初の角度を決めてから順に次々角度を決められる。合計が2πを越えたら駄目。あと途中で長さが足りなくて垂直にできなくなっても駄目。これは二分探索すればよい。
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; double b[10]; int perm[10]; double PI=acos(-1.0); double EPS=1e-9; double solve(int a){ double left=0; double right=PI; for(int i=0;i<100;i++){ double M=(left+right)/2; double th=M; double val=M; for(int j=0;j<a-1;j++){ if(b[perm[(j+a-1)%a]]*cos(th)>b[perm[j+1]]){val=0;break;} double L=acos(b[perm[(j+a-1)%a]]*cos(th)/b[perm[j+1]]); val+=L; th=L; } if(val>2*PI)right=M; else left=M; } double t=right; double s=b[perm[0]]*b[perm[a-1]]*sin(right); double now=t; for(int i=0;i<a-1;i++){ if(b[perm[(i+a-1)%a]]*cos(t)>b[perm[i+1]]+EPS)return 0; double L=acos(b[perm[(i+a-1)%a]]*cos(t)/b[perm[i+1]]); t=L; now+=t; s+=b[perm[i]]*b[perm[i+1]]*sin(t); } if(now>2*PI+EPS)return 0; /*if(s/2>800000){ for(int i=0;i<a;i++)printf("%d ",perm[i]); printf(", %f %f\n",right,s/2); printf("\n"); }*/ return s/2; } int v[10]; int n; double dfs(int a){ double ret=0; if(a>=3)ret=max(ret,solve(a)); if(a<n){ for(int i=0;i<n;i++){ if(v[i])continue; v[i]=1; perm[a]=i; ret=max(ret,dfs(a+1)); v[i]=0; } } return ret; } int main(){ int a; scanf("%d",&a); n=a; for(int i=0;i<a;i++)scanf("%lf",b+i); printf("%.12f\n",dfs(0)); }