Daimayuan Online Judge-跳跳
题目描述
平面上给定了一些整点（横纵坐标均为整数的点），被称为 “魔法阵”。魔法少女派派想要在各魔法阵之间传送，每一次传送，她将使用下面的方式：
刚开始，派派已经位于某传送阵之上；
如果派派掌握一种魔法 \((A,B)\)，其中 \(A,B\) 均为整数。使用一次这个魔法可以让派派从任意整点 \((X,Y)\) 瞬间移动至 \((X+A,Y+B)\)；
选择一种魔法并开始传送，在一次传送过程中可以使用多次该魔法，但在抵达下一个传送阵之前仅能使用这一种魔法。
问派派至少需要掌握多少种魔法，才能在从任意魔法阵直接传送到任意魔法阵？
输入格式
第一行一个整数 \(N\)。
接下来一行 \(N\) 行，每行包含两个整数 \(X_i,Y_i\)， 表示每个魔法阵的坐标。
输出格式
一个数，表示答案。
样例输入1
3
1 1
4 5
1 4
样例输出1
6
解释： 任务是从 \((1,1)\) 传送至 \((4,5)\) 以及 \((1,4)\)、从 \((4,5)\) 传送至 \((1,1)\) 以及 \((1,4)\)、从 \((1,4)\) 传送至 \((1,1)\) 以及 \((4,5)\)。
注意你不能使用 \((0,3)+(3,1)\) 的魔法从 \((1,1)\) 到达 \((4,5)\)。因为每次移动，你只能使用一种魔法。
当然，你可以学习 \((0,1)\)，那样的话，从 \((1,1)\) 到达 \((1,4)\) 则需要使用 \(3\) 次 \((0,1)\) 魔法了。
样例输入2
3
1 1
2 2
1000000000 1000000000
样例输出2
2
数据范围
\(N\in[10,500]\)
\(X_i,Y_i∈[0,10^9]\), 但保证坐标之间两两不同。
解题思路
因为数据范围允许，所有我们以 \(O(n^2)\) 的时间求出所有两点之间的单位向量即可。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
typedef pair<int, int> PII;
#define x first
#define y second
int n;
PII q[N];
int gcd(int a, int b)
{
if(!b) return a;
else return gcd(b, a % b);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d%d", &q[i].x, &q[i].y);
set<PII> cnt;
for(int i = 1; i <= n; i ++)
for(int j = i + 1; j <= n; j ++)
{
int a = q[i].x - q[j].x, b = q[i].y - q[j].y;
int d = gcd(a, b);
cnt.insert({a / d, b / d});
cnt.insert({-a / d, -b / d});
}
printf("%d\n", cnt.size());
return 0;
}