2504 Bounding box

問題概要

正n多角形のうち3つの頂点の座標が与えられる。
正多角形の全ての頂点を含み、各辺が座標軸に平行で面積最小の長方形の面積を求めよ。

解法

正多角形の中心は、正多角形の全ての頂点からの距離が等しい点。
これは与えられた3点から求めることができる。

中心が求まれば、頂点は全て復元できる。
正多角形を含み、辺が座標軸に平行な面積最小の長方形は座標の最大最小を求めれば求まる。

ソースコード

crosspointはspaghetti sourceの

int main(){
	int n,T=0; P p[3];
	while(scanf("%d",&n),n){
		rep(i,3)scanf("%lf%lf",&p[i].real(),&p[i].imag());
		
		P m=(p[0]+p[1])*0.5,M=(p[1]+p[2])*0.5;
		P d=(p[1]-p[0])*P(0,1),D=(p[2]-p[1])*P(0,1);
		P o=crosspoint(L(m,m+d),L(M,M+D));
		
		double a=arg(p[0]-o),r=abs(p[0]-o),da=acos(-1.0)*2/n;
		double X=-INF,x=INF,Y=-INF,y=INF;
		rep(i,n){
			P po=o+r*P(cos(a+da*i),sin(a+da*i));
			double tx=po.real(),ty=po.imag();
			X=max(X,tx); x=min(x,tx);
			Y=max(Y,ty); y=min(y,ty);
		}
		printf("Polygon %d: %.3f\n",++T,(X-x)*(Y-y));
	}
	return 0;
}