幾何コンテストに出てみた。開催時間を勘違いしていて、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の経験が役に立ってるな。