yukicoder : No.2355 Unhappy Back Dance

実装の軽い幾何はいいね。
https://yukicoder.me/problems/no/2355

問題

2次元座標中でN点が指定される。
各点のうち、以下を満たすものはいくつあるか。

• その点からある向きの先に2個以上の点があるような向きがある。

解法

点iが条件を満たす点か判定しよう。
各点jに対し、DX=X[j]-X[i]、DY=Y[j]-Y[i]を考える。
DX,DYを、GCD(|DX|,|DY|)で割った値が一致する点が2個以上ある場合、条件を満たす。

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	int ret=0;
	FOR(i,N) {
		set<pair<ll,ll>> S;
		FOR(j,N) if(j!=i) {
			ll x=X[i]-X[j];
			ll y=Y[i]-Y[j];
			ll g=__gcd(abs(x),abs(y));
			S.insert({x/g,y/g});
		}
		if(S.size()!=N-1) ret++;
	}
	cout<<ret<<endl;
}

まとめ

yukicoderで難易度が下方修正されるのは珍しい？