「ABC226D」 Teleportation

题意

给 \(n\) 组坐标 \((x_i,y_i)\)，你可以选择学习任意一个形式为 \((a_i,b_i)\) 的魔法。

设当前你在 \((x,y)\)，对于每一个魔法 \(i\)，你可以使用它并到达 \((x+a_i,y+b_i)\)。

每个魔法都可以重复使用，求至少需要多少魔法可以让 \(n\) 个坐标互相到达。

分析

从 \((x_1,y_1)\) 到 \((x_2,y_2)\)，需要 \((x_2-x_1,y_2-y_1)\) 的魔法。

为了让魔法的数量尽量少，需要让 \(a\) 和 \(b\) 的最大公因数尽可能大。

取它们的最大公因数为 \(g\)，那么使这两个城市间互相抵达的最佳魔法为 \((\frac{x_2-x_1}{g},\frac{y_2-y_1}{g})\)。

因为不能重合，所以可以用一个 set 去重。

因为两个城市要双向联通，所以最终答案为 set 大小的二倍。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define dbg(x) cout<<#x<<": "<<x<<"\n"
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
const ll mod=1e9+7,maxn=5e2+5,maxt=505;
ll n;
pair<ll,ll>p[maxn];
set<pair<ll,ll> >s;
signed main(){
    n=read();
    for(ll i=1;i<=n;++i){
        p[i].first=read(),p[i].second=read();
    }
    for(ll i=1;i<=n;++i){
        for(ll j=i+1;j<=n;++j){
            ll x=p[j].first-p[i].first,y=p[j].second-p[i].second;
            ll g=__gcd(x,y);
            s.insert({x/g,y/g});
        }
    }
    printf("%lld",s.size()<<1);
    return 0;
}