Codeforces #505 F. Disjoint Triangles

考察ができると、コードは非常に短い。
http://codeforces.com/contest/1025/problem/F

問題

２次元座標上で異なるN点が与えられる。
３頂点以上が一直線上に並ぶことはない。

これらのN点から3点を2組選び、それらで構成される三角形を2つ作るとする。
この時、三角形が共通部分を持たないような点の選び方は何通りか。

解法

２つの三角形について、共通内接線を考える。
これらは3頂点が一直線に無いという条件から、２通りの内接線が考えられ、これらは両三角形の頂点を結ぶものである。
これをもとに数え上げよう。

２頂点A,Bを共通内接線とするような三角形を数え上げることを考える。
AからBの向きに対して左側の２頂点とAが成す三角形と、BからAの向きに対して左側の２頂点とBが成す三角形は、互いにA-Bを共通内接線とする三角形ペアを構成する。

よって、Aを総当たりし、他の頂点をAの頂点に対し偏角ソートしよう。
その後、Bを総当たりしつつ尺取り法の要領で「AからBの向きに対して左側の２頂点」「BからAの向きに対して左側の２頂点」の組み合わせの総和を求めていく。

なお、上記手順は同じ三角形を２回ずつ数えるので最後に２で割ること。

int N;
double X[2020],Y[2020];

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(i,N) {
		vector<double> V;
		FOR(j,N) if(i!=j) V.push_back(atan2(Y[j]-Y[i],X[j]-X[i])), V.push_back(atan2(Y[j]-Y[i],X[j]-X[i])+2*atan(1)*4);
		sort(ALL(V));
		for(x=y=0;x<N-1;x++) {
			while(V[y]-V[x]<atan(1)*4) y++;
			j=y-x-1;
			r=N-2-j;
			ret+=(ll)j*(j-1)/2*r*(r-1)/2;
		}
	}
	cout<<ret/2<<endl;
}

まとめ

勉強になりました。