ABC226
AtCoder Beginner Contest 226 - AtCoder
結果はA~Dの4完。知見を書きます。
D
C++のgcd(m,n)は、|m|と|n|のgcdを返す。どちらかが0の場合、0でない方の数を、どちらも0の場合は0を返す。(参考:
gcd - cpprefjp C++日本語リファレンス
)
この問題では、dx=x[i]-x[j], dy=y[i]-y[j]とすると、それぞれの符号とか0とかで処理を場合分けしなくても、(同じ点に異なる街は存在しないので)、g=gcd(dx,dy)を求めて、dx/=g, dy/=gとするだけでよい。
E
V頂点V辺の無向グラフは「なもりグラフ」と呼ばれ、閉路が1個だけあるグラフになる。(参考: ei1333's page )
この問題では「なもりグラフであるか」だけがわかればいいので、連結成分ごとの頂点数と辺の数が一致するかだけ調べれば良い。
