TopCoderOpen 2016 Round2C Easy BearBall

久々に正の得点を取ってレート回復。
https://community.topcoder.com/stat?c=problem_statement&pm=14323

問題

２次元座標上にN個の頂点がある。
頂点同士を線分でつなぎ、頂点対(X,Y)をつなぎたい。
ただ、線分上の端点以外に他の点が来ることは許可されない。

頂点対の組み合わせN*(N-1)通りそれぞれについて、必要な線分数の総和を求めよ。

解法

全頂点が一直線に並んでいる場合、頂点対の間にある点の数だけ線分をつながないと条件を満たせない。
そうでない場合、(X,Y)の間に他の点が無ければ1本、他の点があれば、XYを結ぶ直線上でない頂点のうち、直線に最も近い点を経由すれば2本で条件を満たせる。

よって、始点Xを総当たりし、Yを傾きごとに分類して同じものの数を求めよう。
各傾きで最寄りの頂点のみ1本で条件を満たすので、傾きがM通りあるなら、始点Xに対し各Yに対する線分数の合計は2*(N-1)-Mとなる。

なお、全頂点が一直線となる場合、XによってM=1となるものがあるので、そこで判定するとラク。

class BearBall {
	public:
	int countThrows(vector <int> X, vector <int> Y) {
		int N=X.size();
		int i,j;
		int ret=0;
		FOR(i,N) {
			set<pair<int,int>> S;
			FOR(j,N) if(i!=j) {
				int dx=X[j]-X[i];
				int dy=Y[j]-Y[i];
				int g=__gcd(abs(dx),abs(dy));
				S.insert({dx/g,dy/g});
			}
			
			if(S.size()==1) {
				ret=0;
				FOR(i,N) FOR(j,N) ret+=abs(i-j);
				return ret;
			}
			ret += 2*(N-1) - S.size();
		}
		
		return ret;
	}
}

まとめ

本番はもう少しややこしいコードで、M=2の場合も真面目に一直線かどうか判定処理してしまった。