kmjp's blog

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

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

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

問題

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

解法

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

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

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

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

まとめ

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

広告を非表示にする