C++11(clang++ 3.9) 解法, 执行用时: 25ms, 内存消耗: 492K, 提交时间: 2020-03-10 12:15:37

#include<cstdio>
#include<cmath>
#include<algorithm>
int n,id[11],lp=0;
double v1,v2,ans=1e10;
struct pos
{
	double x,y;
	void init()
	{
		scanf("%lf%lf",&x,&y);
		
	}
	pos operator +(pos a)
	{
		return (pos){x+a.x,y+a.y};
	}
	pos operator -(pos a)
	{
		return (pos){x-a.x,y-a.y};
	}
	pos operator *(double a)
   {
   	return (pos){x*a,y*a};
   }
   double operator*(pos a)
   {
   	return x*a.y-y*a.x;
   }
   double dot(pos a)
   {
   	return x*a.x+y*a.y;
   }
   double abs()
   {
   	return sqrt(x*x+y*y);
   }
}ps[11];
double mn,mx;
struct line
{
	pos a,b;
	void chk(line w)
	{
		double c=w.b*b;
		if(c==0) return;
		c=(a*w.b+w.b*w.a)/c;
		if(c>0.5) c<mx&&(mx=c);
		else c>mn&&(mn=c);
	}
}ls[15],l0[11];
int main()
{
	scanf("%lf%lf%d",&v1,&v2,&n);
	for(int i=1;i<=n;++i) ps[i].init(),id[i]=i;
	ps[n+1]=ps[1];
	pos p1=(pos){0,0},p2=(pos){v1,0},p3=(pos){v1,v2},p4=(pos){0,v2};
	ls[lp++]=(line){p1,p2-p1};
	ls[lp++]=(line){p2,p3-p2};
	ls[lp++]=(line){p3,p4-p3};
	ls[lp++]=(line){p4,p1-p4};
	for(int i=1;i<=n;++i)
	l0[i]=(line){ps[i],ps[i+1]-ps[i]};
	do
	{
		lp=4;
		double s=0;
		for(int i=1;i<=n;++i)
		{
			int w=id[i];
			mn=-1e10,mx=1e10;
			for(int j=0;j<lp;++j) l0[w].chk(ls[j]);
			ls[lp++]=l0[w];
			s+=(mx-mn)*l0[w].b.abs();
		}
		if(s<ans) ans=s;
	}while(std::next_permutation(id+1,id+n+1));
	printf("%.3f",ans);
	return 0;
}