PKU 1624 This Takes the Cake
http://poj.org/problem?id=1624
四角形のケーキを2つに切り分ける。
このとき、切り分ける線は四角形の4つの頂点か各辺の中点しか通ることができない。
切り分けられたケーキの面積の差が最も小さくなるように切りわけた時の二つの面積を出力しろというような問題。
分け方を全通り試しました。
若干面倒臭い感じでした。
typedef pair<double,double> PD; double tval(PD a,PD b,PD c){ b.F-=a.F; b.S-=a.S; c.F-=a.F; c.S-=a.S; return sqrt((b.F*b.F+b.S*b.S)*(c.F*c.F+c.S*c.S)-pow(b.F*c.F+b.S*c.S,2))/2; } double sval(PD a,PD b,PD c,PD d){ return tval(a,b,c)+tval(a,c,d); } pair<double,double> mid(PD a,PD b){ return mp((a.F+b.F)/2.0,(a.S+b.S)/2.0); } main(){ PI in[4]; int ca=0; while(true){ int nend=0; rep(i,4){ cin>>in[i].F>>in[i].S; nend|=in[i].F|in[i].S; } if(!nend)break; double S=sval(in[0],in[1],in[2],in[3]); double l=0,u=S; rep(i,2){ double tl=sval(in[i],mid(in[i],in[i+1]),mid(in[i+2],in[i+3&3]),in[i+3&3]); l=max(min(tl,S-tl),l); } rep(i,2){ double tl=tval(in[i],in[i+1],in[i+2]); l=max(min(tl,S-tl),l); } rep(i,4){ double tl=tval(in[i],mid(in[i],in[i+1&3]),mid(in[i],in[i+3&3])); l=max(min(tl,S-tl),l); } rep(i,4){ double tl=tval(in[i],in[i+1&3],mid(in[i],in[i+3&3])); l=max(min(tl,S-tl),l); } rep(i,4){ double tl=tval(in[i],mid(in[i],in[i+1&3]),in[i+3&3]); l=max(min(tl,S-tl),l); } printf("Cake %d: %.3f %.3f\n",++ca,l,S-l); } }