yukicoder : No.947 ABC包囲網

他の問題の部分問題で見たことありそう。
https://yukicoder.me/problems/no/947

問題

2次元座標上でN個の点が与えられる。
うち3点を選んで三角形を構築したとき、原点を内部に含むのは何通りか。

解法

2点A,Bを選んだ時、A,Bと原点で対称な点をA',B'とする。
半直線OA'とOB'で囲まれた範囲にある点が3点目の候補となる。

あとは点を偏角ソートしておき、Aを総当たりしつつBを尺取り法で処理すればよい。
座標が大きいのでlong doubleを使っておいた方がよい。

int N;
ll X[4040],Y[4040];


void solve() {
	int i,j,k,l,r,x,y; string s;
	long double pi=4*atan(1);
	
	cin>>N;
	vector<long double> V;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		ll g=__gcd(abs(X[i]),abs(Y[i]));
		if(g==0) {
			i--;
			N--;
			continue;
		}
		X[i]/=g;
		Y[i]/=g;
		V.push_back(atan2(Y[i],X[i]));
		V.push_back(atan2(Y[i],X[i])+2*pi);
		V.push_back(atan2(Y[i],X[i])+4*pi);
	}
	sort(ALL(V));
	ll ret=0;
	FOR(i,N) {
		j=i;
		while(V[j]-V[i]<=pi+1e-12) j++;
		y=j;
		for(x=i+1;x<j;x++) if(V[i]!=V[x]) {
			if(V[x]-V[i]>=pi-1e-12) break;
			while(V[y]-V[x]<pi-1e-12) y++;
			ret+=y-j;
		}
	}
	cout<<ret/3<<endl;
}

まとめ

最初doubleでやって精度不足だった。