kmjp's blog

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

幾何コンテスト2013 : A - 役人

幾何コンテストに出てみた。開催時間を勘違いしていて、35分遅れで参加。
Aは完答でB,Cは部分点止まりだった。
35分の遅れ自体は順位には大きく影響なさそうだけど、時間があればBも解けたかもな。
まだC,Dは解けていないのでA,Bだけ復習。
http://geocon2013.contest.atcoder.jp/tasks/geocon2013_a

問題

300個の点の座標が与えられる。
これらの点を結んで作られる三角形のうち、互いに交わらないものをできるだけ多く作り、その組み合わせを答えよ。
なお、3つ以上の点が一直線に並ぶことはない。

解法

X軸またはY軸方向にソートして、3つずつ組み合わせるだけ。
これで100個の三角形が作れる。
以下のコードではX座標の小さい順に並べている。

pair< pair<int,int>, int> X[301];

void solve() {
	int f,r,i,j,k,l,x,y;
	
	FOR(i,300) {
		cin>>x>>y;
		X[i].first.first=x;
		X[i].first.second=y;
		X[i].second=i+1;
	}
	sort(X,X+300);
	cout<<100<<endl;
	FOR(i,100) _P("%d %d %d\n",X[i*3].second,X[i*3+1].second,X[i*3+2].second);
	
	return;
}

まとめ

このあたりは、以前解いたJOI Open Contest 2012 : B - Jumps - kmjp's blogの経験が役に立ってるな。