考察ができると、コードは非常に短い。
http://codeforces.com/contest/1025/problem/F
問題
2次元座標上で異なるN点が与えられる。
3頂点以上が一直線上に並ぶことはない。
これらのN点から3点を2組選び、それらで構成される三角形を2つ作るとする。
この時、三角形が共通部分を持たないような点の選び方は何通りか。
解法
2つの三角形について、共通内接線を考える。
これらは3頂点が一直線に無いという条件から、2通りの内接線が考えられ、これらは両三角形の頂点を結ぶものである。
これをもとに数え上げよう。
2頂点A,Bを共通内接線とするような三角形を数え上げることを考える。
AからBの向きに対して左側の2頂点とAが成す三角形と、BからAの向きに対して左側の2頂点とBが成す三角形は、互いにA-Bを共通内接線とする三角形ペアを構成する。
よって、Aを総当たりし、他の頂点をAの頂点に対し偏角ソートしよう。
その後、Bを総当たりしつつ尺取り法の要領で「AからBの向きに対して左側の2頂点」「BからAの向きに対して左側の2頂点」の組み合わせの総和を求めていく。
なお、上記手順は同じ三角形を2回ずつ数えるので最後に2で割ること。
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; }
まとめ
勉強になりました。