kmjp's blog

競技プログラミング参加記です

MUJINプログラミングチャレンジ : E - 六角形 / Hexagon

その他コンテスト

これは自力では解けないわ…。
http://mujin-pc-2016.contest.atcoder.jp/tasks/mujin_pc_2016_e

問題

３次元座標において、ある直方体と平面Z=0の共通部分を成す図形が与えられる。
この図形は凸６角形であった。

そのような共通部分を作る可能性のある直方体のうち最小体積を求めよ。

解法

自力では解けそうにないので公式解説を参照。
MUJINプログラミングチャレンジ2016 解説

まずどのような傾きの直方体があり得るかを考える。
前提として、６角形の各辺は、反対側の辺と平行であることを確認する。
次に、６角形の辺を延長した３角形を考えよう。
０～５の入力頂点から、以下のように頂点PQRを求める。
この頂点が鋭角三角形を成すならば、解が存在する。

        1   0
P－－－－－－－－－－Q
 ＼    ／    ＼    ／
   ＼／        ＼／
   2 ＼        ／ 5
       ＼    ／
       3 －－ 4
         ＼／
          R

例えば立方体をABCD-EFGHとする。(ABCDは底面を時計回り、EFGHは反対の面を時計回り、A-Eは辺でつながっている)
このとき例えばこの立方体の断面のうち３頂点からなる３角形を考えると、それがPQRに相当する位置となる。
この立方体の３辺の長さをa,b,cとすると、三平方の定理よりPQ^2 = a^2+b^2、QR^2 = b^2+c^2、RP^2=c^2+a^2の関係があるので、a,b,cの値が分かる。

３辺の長さa,b,cの直方体がPQRを通ることが分かった。
ただ実際の６角形の大きさはそれより小さいので、直方体もそれより小さくて済む。
長さa,b,cの直方体に対し、各面辺12,34,05と平行な位置で面を切り落としても良いので、各辺はP0/PQ、Q1/PQ、P3/PRの大きさとしても良い。
(まぁ図がないと分かりにくいので公式回答の図を見た方が良いと思います。)

地味に鋭角三角形判定の誤差が厳しいので注意。

typedef complex<double> Po;
struct Line {
	Po a,b;
	Line(const Po &a,const Po &b) : a(a),b(b){Rep();};
	void Rep(){
		// assert(a!=b);
		if(a.real()==b.real()) { a.imag(0);b.imag(1); return;} // Y-axis
		Po c,d;
		d.real(1);
		d.imag((b.imag()-a.imag())/(b.real()-a.real()));
		c.imag(b.imag()-b.real()*d.imag());
		d.imag(d.imag()+c.imag());
		a=c; b=d;
	};
};


Po CrossPoint(const Line &l,const Line &r) {
	Po p,ld=l.b-l.a,rd=r.b-r.a,d3=l.b-r.a;
	double aa=ld.real()*rd.imag()-ld.imag()*rd.real();
	double bb=ld.real()*d3.imag()-ld.imag()*d3.real();
	if(abs(aa)<1e-9 && abs(bb)<1e-9) return Po(1e9,-1e9); //same
	if(abs(aa)<1e-9) return Po(1e9,1e9); //parallel
	return r.a+bb/aa*(r.b-r.a);
};

ll X[7],Y[7];

void solve() {
	int i,j,k,l,x,y; string s;
	
	FOR(i,6) cin>>X[i]>>Y[i];
	X[6]=X[0],Y[6]=Y[0];
	
	FOR(i,3) {
		ll dx1=X[i+1]-X[i];
		ll dy1=Y[i+1]-Y[i];
		ll dx2=X[i+4]-X[i+3];
		ll dy2=Y[i+4]-Y[i+3];
		if(dx1*dy2-dx2*dy1!=0) return _P("-1\n");
	}
	
	Line L1(Po(X[0],Y[0]),Po(X[1],Y[1]));
	Line L2(Po(X[2],Y[2]),Po(X[3],Y[3]));
	Line L3(Po(X[4],Y[4]),Po(X[5],Y[5]));
	Po P=CrossPoint(L1,L2);
	Po Q=CrossPoint(L2,L3);
	Po R=CrossPoint(L1,L3);
	double PQ=norm(P-Q);
	double QR=norm(Q-R);
	double RP=norm(R-P);
	
	if(PQ+QR-1e-8<RP) return _P("-1\n");
	if(PQ+RP-1e-8<QR) return _P("-1\n");
	if(QR+RP-1e-8<PQ) return _P("-1\n");
	
	double A = sqrt((PQ+RP-QR)/2);
	double B = sqrt((PQ+QR-RP)/2);
	double C = sqrt((QR+RP-PQ)/2);
	double V=A*B*C;
	V *= abs(Po(X[0],Y[0])-P)/abs(R-P);
	V *= abs(Po(X[1],Y[1])-R)/abs(R-P);
	V *= abs(Po(X[3],Y[3])-P)/abs(Q-P);
	_P("%.12lf\n",V);
}

まとめ

本番中はそもそも問題を誤読していたので解けるはずがなかった。