AOJ2373 HullMarathon

見た目怖いけど実は簡単。各うさぎの偏角ソート順が分かればあとは隣り合う2つの角度を面積が大きくなるように山を登って行くだけなので偏角ソート順を全探索する。隣接する角度の和がpiより大きい場合にちょっと面倒なので微分の零点とかせずに適当に三分探索しています。
遅すぎるうさぎはちゃんと無視してやらないといけない。何も考えずに書いたらTLEしたので円順列の一点を固定して余計な探索を消してAC。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
double pi=3.14159265358979323;
typedef pair<double,double>pdd;
pdd get(double a,double b,double t)
{
	double beg,end;
	if(t<pi)
	{
		beg=0;
		end=t;
	}
	else
	{
		beg=t-pi;
		end=pi;
	}
	for(int p=0;p<30;p++)
	{
		double m1=(beg+beg+end)/3.0,m2=(beg+end+end)/3.0;
		if(a*sin(m1)+b*sin(t-m1)<a*sin(m2)+b*sin(t-m2))
		{
			beg=m1;
		}
		else
		{
			end=m2;
		}
	}
	return make_pair(beg,t-beg);
}
int cnt=0;
double calc(vector<double>vec)
{
	vector<double>ret;
	for(int i=0;i<vec.size();i++)
	{
		ret.push_back(pi*2.0/double(vec.size()));
	}
	for(int p=0;p<30;p++)
	{
		for(int i=0;i<vec.size();i++)
		{
			pdd zan=get(vec[i]*vec[(i+1)%vec.size()],vec[(i+1)%vec.size()]*vec[(i+2)%vec.size()],ret[i]+ret[(i+1)%vec.size()]);
			ret[i]=zan.first;
			ret[(i+1)%vec.size()]=zan.second;
		}
	}
	double ans=0;
	for(int i=0;i<vec.size();i++)
	{
		ans+=vec[i]*vec[(i+1)%vec.size()]*sin(ret[i])/2.0;
	}
	return ans;
}
double maxi=0;
void calc2(vector<double>vec,vector<bool>now,vector<double>ans,int beg)
{
	for(int i=beg+1;i<vec.size();i++)
	{
		if(!now[i])
		{
			now[i]=true;
			ans.push_back(vec[i]);
			if(ans.size()>=3)
			{
				maxi=max(maxi,calc(ans));
			}
			calc2(vec,now,ans,beg);
			ans.pop_back();
			now[i]=false;
		}
	}
}
int main()
{
	int num;
	scanf("%d",&num);
	vector<double>vec;
	for(int i=0;i<num;i++)
	{
		double zan;
		scanf("%lf",&zan);
		vec.push_back(zan);
	}
	vector<bool>z;
	z.resize(vec.size());
	vector<double>a;
	fill(z.begin(),z.end(),false);
	for(int i=0;i<vec.size();i++)
	{
		z[i]=true;
		a.push_back(vec[i]);
		calc2(vec,z,a,i);
		z[i]=false;
		a.pop_back();
	}
	printf("%lf\n",maxi);
}

新年初AC。なんで700なんだろう。