回旋星空

Ch_Zaqdt

发布于 2019-01-10 11:32:13

5890

发布于 2019-01-10 11:32:13

文章被收录于专栏：Zaqdt_ACMZaqdt_ACM

题目链接： https://www.nowcoder.com/acm/contest/90/E

题意就是比如有三个点a,b,c，以b为转折点，有a到b的距离等于b到c的距离的话就说明这是一个回旋图标，但这要算两次，因为a->b->c和c->b->a算两个图形。思路就是先输入每个点的坐标，然后从第一个点开始遍历求出该点到所有点的距离，用数组dis存下来，然后sort排序一下，然后记录有多少个相等的边，因为考虑到刚才说的那种算两次的情况，所以对相等的边进行全排列。

AC代码：

#include <bits/stdc++.h>
using namespace std;
struct Node{
  int x,y;
}Edge[100005];
int dis[100005];
int n,m;

int dist(int x1,int y1,int x2,int y2){
  return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main()
{
  scanf("%d",&n);
  while(n--){
    int sum = 0;
    scanf("%d",&m);
    for(int i=0;i<m;i++){
      scanf("%d%d",&Edge[i].x,&Edge[i].y);
    }
    for(int i=0;i<m;i++){
      int num = 0;
      memset(dis,0,sizeof(dis));
      for(int j=0;j<m;j++){
        dis[num++] = dist(Edge[i].x,Edge[i].y,Edge[j].x,Edge[j].y);
    }
    sort(dis,dis+num);
    int ans = 1;
    for(int k=1;k<num;k++){
      if(dis[k] == dis[k-1])ans++;
      else{
        sum += ans*(ans-1);        // 全排列
        ans = 1;                   // 当一个长度计算完后初始化ans，然后继续计算下一个长度的个数
      }
    }
    sum += ans*(ans-1);
  }
    if(!sum)printf("WA\n");
    else printf("%d\n",sum);
  }
  return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018年03月26日，如有侵权请联系 cloudcommunity@tencent.com 删除

sort