PKU 2504 Bounding box
http://poj.org/problem?id=2504
正n角形の3つの頂点の座標が与えられるので、その正n角形をすっぽりと覆う、最小の長方形の面積を答えるというような問題。
ただし、長方形の辺はx軸、y軸に平行とする。
http://www.nn.iij4u.or.jp/~hsat/misc/math/centre/circumcentre.html
外心を求めるのが面倒だったのでこのサイトから式を持ってきました。
いろいろとはまった挙句にサンプルが通ってもWAなので、よくみてみるとPlolygonとかになっていました。
typedef pair<double,double> vec2; vec2 operator+(const vec2&l,const vec2&r){ return vec2(l.F+r.F,l.S+r.S); } vec2 operator*(const double &l,const vec2&r){ return vec2(l*r.F,l*r.S); } vec2 operator*(const vec2 &l,const double&r){ return r*l; } vec2 operator/(const vec2 &l,const double &r){ return vec2(l.F/r,l.S/r); } vec2 operator-(const vec2&l,const vec2&r){ return vec2(l.F-r.F,l.S-r.S); } double operator*(const vec2&l,const vec2&r){ return l.F*r.F+l.S*r.S; } double norm2(vec2 in){ return in.F*in.F+in.S*in.S; } main(){ int n; int po=0; while(cin>>n,n){ ++po; vec2 in[3]; rep(i,3)cin>>in[i].F>>in[i].S; double ed[3]; rep(i,3)ed[i]=norm2(in[(i+2)%3]-in[(i+1)%3]); vec2 a=in[1]-in[0],b=in[2]-in[0]; double s2=(norm2(a)*norm2(b)-(a*b)*(a*b))/4; vec2 q=mp(0,0); rep(i,3){ double add=0; rep(j,3){ if(i==j)add-=ed[j]; else add+=ed[j]; } add*=ed[i]; q=q+in[i]*add; } q=q/(16*s2); double theta=atan2(in[0].S-q.S,in[0].F-q.F); double r=sqrt(norm2(in[0]-q)); double maxx=in[0].F,maxy=in[0].S,minx=in[0].F,miny=in[0].S; rep(i,n){ vec2 np=q+vec2(r*cos(theta+i*2*pi/n),r*sin(theta+i*2*pi/n)); maxx=max(maxx,np.F); maxy=max(maxy,np.S); minx=min(minx,np.F); miny=min(miny,np.S); } printf("Polygon %d: %.3f\n",po,(maxx-minx)*(maxy-miny)); } }