1322: 同心共筑中国梦

这道题有2000个样例的话，N3的话会时间超限，需要想到用距离来判断外心。现在复杂度是n2

#include <bits/stdc++.h>
using namespace std;
const int N=2010;
long x[N],y[N];
long long dist[N][N];
int main(){int mod=2333;int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld %lld",&x[i],&y[i]);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dist[i][j]=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]);}}int ans=0;for(int i=1;i<=n;i++){sort(dist[i]+1,dist[i]+1+n);int k=1;for(int j=3;j<=n;j++){ // 因为dist[i][1]一定是第i个点与自己的距离 if(dist[i][j]==dist[i][j-1]){k++;}else{if(k>=3){ans+= k*(k-1)*(k-2)/6;}k=1;}if(j==n){ //如果遍历最后一个时，发生了相同，这时候要尝试输出一下答案，如果发生了不同，k=1时，ans只会加0； ans+= k*(k-1)*(k-2)/6;}}}printf("%d",ans);
}