Codeforces #308 Div2 D. Vanya and Triangles

O(N^3)でいいの…。
http://codeforces.com/contest/552/problem/D

問題

２次元座標上にN個の異なる格子点の座標が指定される。

このうち３点を選び、面積が0にならない三角形を作る方法は何通りあるか。

解法

実はこれ愚直にO(N^3)で総当たりして面積を求めても間に合う。
ここではO(N^2*logN)解を紹介。

まず1点を総当たりする。仮にこれを点Aとする。
次に、他の点について点Aと結んだ時の偏角(tanの値でも良い)を求め、同じ偏角のものを数え上げる。
三角形を作る場合点A以外に2点選ぶ選び方は[tex: {}_{N-1} C_2}通り。
ただしそこから偏角が同じ2点を選ぶパターンを引けばよい。

また、上記方法では同じ点を三重にカウントしているので、最後に3で割ると良い。

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	ll ret=0;
	FOR(x,N) {
		map<pair<int,int>,int> M;
		FOR(y,N) if(x!=y) {
			int dx=X[y]-X[x],dy=Y[y]-Y[x];
			if(dx==0) dy=1;
			else if(dy==0) dx=1;
			else {
				int g=__gcd(abs(dx),abs(dy));
				dx/=g, dy/=g;
				if(dx<0) dx=-dx,dy=-dy;
			}
			M[make_pair(dx,dy)]++;
		}
		ret += (N-1)*(N-2)/2;
		FORR(r,M) ret -= (r.second)*(r.second-1)/2;
	}
	
	cout<<ret/3<<endl;
}

まとめ

O(N^3)が通ってしまいHackミスした。
今回ここまで18分で通ってる。Div2にしても簡単でない？