13景驰回旋星空

星空"/>

13景驰回旋星空

链接：
来源：牛客网

题目描述

曾经有两个来自吉尔尼斯的人(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行,每行跟两个整数x_i和y_i表示每个星星的坐标(-10000< x_i, y_i<10000)

输出描述:

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

示例1

输入

2
2
1 0
0 1
3
1 0
0 1
0 0

输出

WA
2

备注:

没有重复的星星，且选中的三个星星是互相不一样的（即下标不同）
欧氏距离即直线距离

代码：

#include<iostream> #include<bits/stdc++.h> #include<math.h> using namespace std; struct po      //点结构体 {      int x;      int y; }; double dis[1000];//距离 double di( int a, int b, int c, int d) {      return sqrt ((a-c)*(a-c)+(b-d)*(b-d));//距离 } int main() {      int t,n;      cin>>t;      while (t--)      {          cin>>n;                struct po a[1010];          for ( int i=0;i<n;i++)          {              cin>>a[i].x>>a[i].y;          }          if (n<3)          {              cout<< "WA" <<endl;              continue ;          }          int ans=0,q=1;          for ( int i=0;i<n;i++)          {                int h=0;              memset (dis,0, sizeof (dis));              for ( int j=0;j<n;j++)              {                  if (i!=j)                  {                      dis[h++]=di(a[i].x,a[i].y,a[j].x,a[j].y);                  }              }              sort(dis,dis+h);              for ( int i=0;i<h-1;i++)              {                  if (dis[i]==dis[i+1])                  {                      q++;                  }                  else                  {                      ans+=q*(q-1)/2;                      q=1;                  }              }            }          if (ans==0)          {              cout<< "WA" <<endl;          }          else          cout<<ans*2<<endl;      } }

理解：先求得一个点到各个点距离，然后算相同的距离，用公式q*(q-1)/2得到

一个点为中点可以得到的等腰三角形；

相加为ans,最后要乘以二。