Wunder Fund Round 2016 : C. Constellation

一応レートは上がったけども、直前でEを逃すなど微妙な出来。
http://codeforces.com/contest/618/problem/C

問題

２次元座標上でN個の点が与えられる。
ここ3点を選ぶ選び方のうち、３点が成す三角形の内部に他の点が入らないものを答えよ。

解法

本番取った解法は、まず0番の点とそこから最近点pを求める。
後は残りの点に対し、0-pを伸ばした直線との距離を求め、非負で最短となる点を求めた。

別の方法としては頂点群を座標順にpairwiseでソートし、連続する３点のうち面積が0にならないものを選べぶ手段もあるようだ。
以下は後者。

int N;
pair<ll,ll> V[101010];
map<pair<ll,ll>,int> MP;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>V[i].first>>V[i].second,MP[V[i]]=i+1;
	sort(V,V+N);
	FOR(i,N) {
		if((V[i+2].first-V[i].first)*(V[i+1].second-V[i].second)
		 != (V[i+1].first-V[i].first)*(V[i+2].second-V[i].second))
		 	return _P("%d %d %d\n",MP[V[i]],MP[V[i+1]],MP[V[i+2]]);
	}
}

まとめ

今回C,Dは落とした人が多かったので、そこを通せたのは良かった。