yukicoder : No.1144 Triangles

これは典型な気がするな…。
https://yukicoder.me/problems/no/1144

問題

2次元座標上でN個の格子点の座標が与えられる。
3点を選んだ時の面積の総和の2倍を答えよ。

解法

三角形ABCに対し、ベクトルACがABより左を向いているとき、
(BX-AX)*(CY-AY)-(BY-AY)*(CX-AX)
の総和を取ればよい。

そこで、中心を1つ定め偏角ソートしよう。
例えばAを中心に偏角ソートしたとき、∠BACが180度以内となる複数のCにおける(CY-AY)と(CX-AX)の総和を取れば、これらの三角形ABCの面積の総和を一気に取れる。
Bを角度順に走査するのに合わせ、尺取り法の要領でCの範囲をずらしていく。

なお、この処理では同じ三角形を3回ずつ足し合わせるので、最後に3で割る。

int N;
int X[2020],Y[2020];
const ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	double pi=atan(1)*4;
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	
	ll ret=0;
	FOR(i,N) {
		vector<pair<double,int>> V;
		FOR(j,N) if(X[i]!=X[j]||Y[i]!=Y[j]) {
			double t=atan2(Y[j]-Y[i],X[j]-X[i]);
			if(t<0) t+=2*pi;
			V.push_back({t,j});
			V.push_back({t+2*pi,j});
		}
		sort(ALL(V));
		ll SX=0,SY=0;
		int L=0,R=0;
		FOR(L,V.size()/2) {
			if(V[L].first>=2*pi) break;
			double t=V[L].first;
			x=V[L].second;
			while(V[R].first<t+pi) {
				SX+=(X[V[R].second]-X[i]);
				SY+=(Y[V[R].second]-Y[i]);
				R++;
			}
			
			(ret+=(X[x]-X[i])*SY-(Y[x]-Y[i])*SX)%=mo;
			SX-=X[x]-X[i];
			SY-=Y[x]-Y[i];
			
		}
	}
	
	cout<<(ret%mo+mo)*((mo+1)/3)%mo<<endl;
	
}

まとめ

何度か見てそう。