20 分做法

20 分留给暴力。可以枚举所有两个点对 $(x_i, y_i)$ 和 $(x_j, y_j)$ ，把从 $i$ 点到 $j$ 点的咒语 $(x_i - x_i, y_j - x_j)$ 记下来。这样一共有 $n ^ 2$ 个咒语。

之后枚举子集，判断这 $n^2$ 个咒语中最少选出哪些可以满足条件即可。

因此，时间复杂度为 $O(3^{n^2})$

100 分做法

以样例2为例。为了在每对米奇妙妙屋之间旅行，需要$(\pm 1,0)$，$(\pm 2,0)$，$(\pm 3,0)$，但后两个移动实际上是不必要的，因为可以通过多次重复$(\pm 1,0)$来实现。

设 $(X,Y)$ 为从米奇妙妙屋 $i$ 到米奇妙妙屋 $j$ 旅行时坐标的变化量。此外，假设 $X$ 和 $Y$ 都能被 $d$ 整除。那么，与其记住咒语$(X,Y)$，不如记住$(\frac{X}{d},\frac{Y}{d})$。

因此，一旦我们知道了坐标的变化量$(X,Y)$，我们可以将它们除以相同的数字，直到$X$和$Y$不再有大于或等于$2$的公共因子为止，以确定要记住的咒语。实际上，

可以通过将$X$和$Y$除以它们的最大公约数(GCD)来找到这个咒语。

通过以上观察，我们可以证明对于每一对不同的米奇妙妙屋$(i,j)$执行以下操作是最优的。

考虑从$(x_i,y_i)$到$(x_j,y_j)$的旅行。

首先，令$X=x_j−x_i$，$Y=y_j−y_i$。然后，令$g=\text{gcd}(X,Y)$，并将其转化为$X \leftarrow \frac{X}{g}$，$Y \leftarrow \frac{Y}{g}$。最后，记住咒语$(X,Y)$。

$\text{gcd}(X,Y)$的时间复杂度为$O(\log(\max(X,Y)))$。因此，问题的总时间复杂度为$O(N^2 \log(\max(X,Y)))$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair < int, int > PII;
const int SIZE = 5e2 + 5;
int n;
map < PII, int > vis;
struct node {
    int x, y;
} a[SIZE];
int main() {
   //freopen("mantra.in", "r", stdin);
    //freopen("mantra.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i].x >> a[i].y;
    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            if (i == j) continue;
            int x = a[i].x - a[j].x, y = a[i].y - a[j].y;
            int d = __gcd(x,y); d = abs(d);
            x /= d, y /= d;
            if (!vis[(PII) {x, y}]) vis[(PII) {x, y}] = 1, ++ ans;
            	//cout << x << " " << y << endl;
        }
    }
    printf("%lld\n", ans);
    return 0;
}