AOJ 2373: HullMarathon

今日もブログに記事を書きます 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));
}