東京工業大学プログラミングコンテスト2015 : H - 包囲

なんか無駄に面倒な解き方ばかりしてるなぁ。
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_h

問題

２次元座標上でN個の異なる位置の格子点が与えられる。
これらのうち一部を結んで得られる多角形のうち、原点を囲み、かつ面積が正のものの中で最小値を求めよ。

解法

条件を満たす多角形は以下のどちらか。

• 三角形
• 対角線が原点で交わる四角形

N≦200なので三角形のケースはO(N^3)通り格子点を総当たりすればよい。
四角形のケースも、２点の間の線分が原点を通るような２点を列挙すれば、あとはその２点を結んだ直線をまたいだ両側はそれぞれ個別に最小の３角形を２つ構成するようにすればよいからやはりO(N^3)。

ただ、自分は上記条件に自信が持てず別解法で解いた。
まず頂点を偏角でソートする。
各点を始点とし、反時計回りで点を結んでいきながらそれらが構成する面積の和を最小化するDPを解く。
状態としてはdp[始点][最後の点] := (始点～最後の点のうちいくつかを結んだ線分群と、(始点-原点)及び(最後の点-原点)を結んでできる図形のうち面積の最小値)として１周結んでいけばよい。
こちらもO(N^3)。

int N;
ll X[303],Y[303];
double ret=1e11;
pair<double,pair<int,int>> P[202];

double dp[301];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		P[i]={atan2(Y[i],X[i]),{X[i],Y[i]}};
	}
	sort(P,P+N);
	FOR(i,N) X[i]=P[i].second.first,Y[i]=P[i].second.second;
	
	FOR(i,N) {
		FOR(x,N+1) dp[x]=1e11;
		dp[0]=0;
		for(y=1;y<=N;y++) {
			FOR(x,y) {
				ll a=(X[(x+i)%N]*Y[(y+i)%N]-X[(y+i)%N]*Y[(x+i)%N]);
				if(a>0) dp[y]=min(dp[y],dp[x]+a/2.0);
			}
		}
		ret=min(ret,dp[N]);
	}
	
	if(ret==1e11) _P("Impossible\n");
	else _P("Possible\n%.12lf\n",ret);
}

まとめ

今回想定解より回りくどい解き方してるのが多い。