链接：https://www.nowcoder.com/acm/contest/90/E
来源：牛客网

题目描述

曾经有两个来自吉尔尼斯的人(A和C)恋爱了,他们晚上经常在一起看头上的那片名为假的回旋星空,

有一天他们分手了,A想通过回旋星空测量他们之间的复合指数,测量的规则是,

计算回旋图标的个数,即选中三颗星星,分别作为回旋图标的起点,拐点和终点,假设现在有三个

星星分别为i,j,k,如果d(a[i],a[j]) == d(a[j],a[k])则表示找到了一个回旋图标,其中d(x,y)表示这两个点的欧氏距离

为了给它很大的希望(i,j,k)和(k,j,i)被认为是两个不同的回旋图标

 

A花了一晚上终于把整片星空映射到了一张二平面图上,由于星星太多以至于A有点懵逼,所以

你能帮帮他吗,要不然他可能真的WA的一声哭了出来
作为埃森哲公司的一员，你在解决问题的同时也向A介绍了埃森哲公司的业务范围。
为了全方位地满足客户的需求，正在不断拓展自身的业务服务网络，包括管理及信息技术咨询、企业经营外包、企业联盟和风险投资。除了以产品制造业、通信和高科技、金融服务、资源、政府机构等不同行业划分服务内容之外，还从以下几方面提供咨询服务：
1.客户关系管理
2.业务解决方案
3.电子商务
4.供应链管理

输入描述:

第一行一个整数T(T<=10),表示组数

对于每组数据有一个n,表示有n个小星星(0< n < 1000)

接下来跟着n行,每行跟两个整数xi和yi表示每个星星的坐标(-10000< xi, yi<10000)

输出描述:

对于每组数据,如果没有找到回旋图标输出”WA”,否则输出找到图标个数

如果遍历三个点的话时间复杂度是n^3,会超时；

考虑降低时间复杂度，我们可以遍历有一个公共顶点的两条边，找出两条边相等的样例；

因为是稠密图，所以用邻接矩阵来存图，如果是稀疏图的话，可以考虑链式前向星存图；

代码如下

#include<stdio.h>
#include<algorithm> 
#include<math.h>
using namespace std;
/*
链接：https://www.nowcoder.com/acm/contest/90/E
来源：牛客网

2
2
1 0
0 1
3
1 0
0 1
0 0
输出

WA
2
备注:
没有重复的星星，且选中的三个星星是互相不一样的（即下标不同）
欧氏距离即直线距离
*/
const int INF=1005;
double data[INF];
double Distance(double x1,double y1,double x2,double y2);
int   count1(int a);
int main()
{
	int t;
	scanf("%d",&t);
	int n;
	while(t--)
	{
		scanf("%d",&n);
		int tempMap[INF][2];
		for(int i=1;i<=n;i++)
		scanf("%d %d",&tempMap[i][0],&tempMap[i][1]);
		int result=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i!=j)
				data[j]=Distance(tempMap[i][0],tempMap[i][1],tempMap[j][0],tempMap[j][1]);
				else
				data[j]=-1;
			}
			sort(data+1,data+1+n);
			data[n+1]=-1;
			double temp=data[2];
			int result1=0;
			for(int k=2;k<=n;k++)
			{
				if(data[k]==temp)
				result1++;
				if(data[k+1]!=temp)
				{
					result+=count1(result1)*2;
					temp=data[k+1];
					result1=0;
				}
				

			}
			
		}
		if(result==0)
		printf("WA\n");
		else
		printf("%d\n",result);
		
	}
	
	
	
	return 0;
}
double Distance(double x1,double y1,double x2,double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int count1(int a)
{
	if(a<2)
	return 0;
	return (a*(a-1))/2;
}