AT_abc418_e 题解

· · 题解

题目传送门

题意

平面内有 N 个点，不存在两点重合或三点共线的情况，求平面内梯形的数量。

思路

因为一组对边平行的四边形是四边形，那么在平面中斜率相同的边平行，就可以组成梯形。注意到 N\le2000，可以暴力求出每一条边的斜率。设共有 K 不同的斜率，每个斜率有 C 条边，每两条边一一搭配，共有 \sum_{i=1}^k\frac{C(C-1)}{2} 组互相平行的边。

然而上述的式子并不是答案，因为存在两组对边互相平行的平行四边形，这也导致平行四边形的数量被计算了 2 次。减掉平行四边形的方法也不难想，因为平行四边形的对角线互相平分，只需要在平行的边中减去即可。同样是每两条边一一搭配，计算方法同上。

最终时间复杂度略大于 \mathcal{O}(N^2)，N^2 是暴力枚举每条边的复杂度，略大于是因为存储的时候用到的 STL 容器带来的较大的常数。

注意事项

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=2e3+10,INF=1e9;
int x[N],y[N];
struct node{
    int u,v;
};
int to(int u,int v){
    return u*INF+v;
}
node bk(int x){
    return (node){x/INF,x%INF};
}
unordered_map<int,vector<node>>mp;
signed main(){
    int n=read();
    for(int i=1;i<=n;++i)
        x[i]=read(),y[i]=read();
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j){
            int dx=x[i]-x[j],dy=y[i]-y[j];
            if(!dx&&!dy)
                continue;
            int _gcd=__gcd(dx,dy);
            dx/=_gcd,dy/=_gcd;
            if(dx<0||!dx&&dy<0)
                dx=-dx,dy=-dy;
            mp[to(dx,dy)].push_back({i,j});
        }
    int cnt=0;
    for(auto[u,v]:mp){
        unordered_map<int,int>t;
        for(auto[x,y]:v)
            ++t[x],++t[y];
        int sum=0;
        for(auto[x,y]:t)
            sum+=y*(y-1)/2;
        int l=v.size();
        cnt+=l*(l-1)/2-sum;
    }
    unordered_map<int,int>t;
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j){
            int sx=x[i]+x[j],sy=y[i]+y[j];
            ++t[to(sx,sy)];
        }
    int res=0;
    for(auto[u,v]:t)
        res+=v*(v-1)/2;
    printf("%lld\n",cnt-res);
    return 0;
}