给定圆上一些点求组成矩形个数

例题传送门

可以\(C_n^{4}\)暴力枚举四个点，根据前缀和计算4条边判断。

但是发现矩形的对角线是一定经过圆心的，而且任意两条直线可以组成一个矩形。

那我们\(C_n^2\)枚举点，用前缀和算出两点间圆弧距离，为圆周长一半就是直径。

最后答案是\(直径数*(直径数-1)/2\)

当然，当圆周长是奇数时无解，因为这里给出的点都是整点

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=22;
int n,sumn,ans,a[maxn],pre[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sumn+=a[i];
        pre[i]=pre[i-1]+a[i];   
    }   
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    for(int q=j+1;q<=n;q++)
    for(int w=q+1;w<=n;w++)
    {
        int a=pre[i]+pre[n]-pre[w],b=pre[j]-pre[i];
        int c=pre[q]-pre[j],d=pre[w]-pre[q];
        if(a==c&&b==d)  ans++;
    }
    cout<<ans;
    //另一种方法 
/*  for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
        if(pre[j]-pre[i]==sumn/2)   ans++;//判断直径
    cout<<(sumn%2==1?0:ans*(ans-1)/2); /*周长奇数就是0*/ 
}