AtCoder Beginner Contest 226 D - Teleportation - yokobuttonの不定期で競技プログラミングをするブログ

問題の要約
　直交座標の上にN個の街があり,1,2,...,Nと番号がつけられている。
　街iは地点(xi,yi)にあり,2つの異なる番号の街が同じ座標にあることはない。
　魔法があり,魔法は整数の組(a,b)によって識別されていて,地点(x,y)にいるときに魔法(a,b)を使うと,(x+a,y+b)にワープすることができる。
　任意の整数の組(a,b)を選んで魔法(a,b)を覚えることができ,また,何種類でも魔法を覚えることができる。
　全ての相異なる街の組(i,j)について次の行動をとれるようにいくつかの魔法を覚えることにした。
　　・覚えた魔法のうち1種類のみを選ぶ。その後,選んだ魔法のみを繰り返し使って街iから街jに移動する。
　少なくとも何種類の魔法を覚えればよいか?
制約
　2<=N<=500
　0<=xi<=10^9(1<=i<=N)
　0<=xj<=10^9(1<=j<=N)
　i≠jならば(xi,yi)≠(xj,yj)

考え方
　1,街の番号を1つずらす
　　1<=i,j<=N => 0<=i,j<=N-1
　2,街iから街jに移動するときの魔法を考える。
　　街iが(xi,yi),街jが(xj,yj)にあるときに覚えなければいけない魔法(a,b)は(xj-xi,yj-yi)である。
　　これを使うと街iの地点で(a,b)を使うと(xi+xj-xi,yi+yj-yi)=(xj,yj)となって街jに移動できる。
　3,逆に街jから街iに移動するときの魔法を考える。
　　同じように覚えなければいけない魔法(a,b)は(xi-xj,yi-yj)である。
　4,この2つを全ての組み合わせで行う。
　　NC2=N1/(N-2)!/2!=N(N-1)/2である。
　　Nの最大値は500なので,N(N-1)/2=500*499/2=124750で計算量的に大丈夫そう。
　5,魔法を重複のないように覚えたい。
　　これにはC++ではmapを使う。
　6,これで実装してみる。
#include<iostream>
#include<map>
#include<vector>

using namespace std;

cout << magic.size() << endl;

return 0;
}
　7,結果WAになる。
　8,何がダメだったのか考えてみる。
　　問題文や入力例でもあるとおり,街iから街jに行くときに魔法は何回使ってもよい。
　　よって,何かの数値でa,bを割ればよさそう。
　　aとbが2で割れるとき,2回魔法を使えばよい。
　　aとbが3で割れるとき,3回魔法を使えばよい。
　　.
　　.
　　.
　　aとbは何で割ればよいか?
　　aとbが割れる最大の値で割ればよい。
　　これは最大公約数が使える。
　9,aとbを最大公約数で割った値を魔法として覚えるとして実装する。
　10,結果REする。
　11,おそらく0除算しているので,aが0とbが0とそれ以外で条件分岐する。

実際のプログラム
#include<iostream>
#include<cstdlib>
#include<map>
#include<vector>

using namespace std;

long long gcd(long long a, long long b){
if(a % b == 0){
return b;
}else{
return gcd(b, a%b);
}

}

int main(){
long long N;
cin >> N;
vector<pair<long long, long long>> xy(N);
for(long long i = 0; i < N; i++){
cin >> xy[i].first >> xy[i].second;
}

map<pair<long long, long long>, long long> magic;
for(long long i = 0; i < N; i++){
for(long long j = i+1; j < N; j++){
if(xy[j].first-xy[i].first == 0 ){
pair<long long, long long> ij = make_pair(0, 1);
magic[ij] = 1;
pair<long long, long long> ji = make_pair(0, -1);
magic[ji] = 1;
}else if(xy[j].second-xy[i].second == 0){
pair<long long, long long> ij = make_pair(1, 0);
magic[ij] = 1;
pair<long long, long long> ji = make_pair(-1, 0);
magic[ji] = 1;
}else{
long long gcd_num = gcd(llabs(xy[j].first-xy[i].first), llabs(xy[j].second-xy[i].second));
pair<long long, long long> ij = make_pair((xy[j].first-xy[i].first)/gcd_num, (xy[j].second-xy[i].second)/gcd_num);
magic[ij] = 1;
pair<long long, long long> ji = make_pair((xy[i].first-xy[j].first)/gcd_num, (xy[i].second-xy[j].second)/gcd_num);
magic[ji] = 1;
}
}
}

cout << magic.size() << endl;

return 0;
}