Codeforces #346 Div2. D. Bicycle Race

Cをしょうもない配列外参照で落としたのが痛いけど、Gが本番中に解けて良かった。
http://codeforces.com/contest/659/problem/D

問題

2次元座標上で、格子点をつないだ形状の池がある。
この池の境界は各辺X軸かY軸に並行である。

この池の周囲を回るとき、90度向きを変えないと即座に池に落ちてしまうようなポイントはいくつあるか。

解法

今回の問題文の設定では池を時計回りに回るため、池の境界を周る際左に曲がらないといけないポイントは、題意のポイントとなる。
そこであとは左曲りのポイントを数えよう。

int N;
int X[1010],Y[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N+1) cin>>X[i]>>Y[i];
	FOR(i,N+1) X[N-i]-=X[0],Y[N-i]-=Y[0];
	
	int ret=0;
	for(i=1;i<N;i++) {
		if(X[i]-X[i-1]>0&&Y[i+1]>Y[i]) ret++;
		if(X[i]-X[i-1]<0&&Y[i+1]<Y[i]) ret++;
		if(Y[i]-Y[i-1]>0&&X[i+1]<X[i]) ret++;
		if(Y[i]-Y[i-1]<0&&X[i+1]>X[i]) ret++;
	}
	cout<<ret<<endl;
	
}

まとめ

なんで微妙にO(N^2)が通りそうな入力上限にしたんだろうな。