欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

nowcoder 90 E-回旋星空

程序员文章站 2024-03-15 21:34:18
...

题目

题目链接

题目描述
曾经有两个来自吉尔尼斯的人(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”,否则输出找到图标个数

示例1
输入

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

输出

WA
2


分析

这题乍一看似乎无从下手,要直接寻找两个距离相同的点并不容易,但由于数据量不是很大,不妨先把所有点两两之间的距离计算并保存到数组里面,通过排序直接对距离相同的点进行计数。
对每个点,计算其他n-1个点到他的距离并排序,到该点距离相同的点就排到一起了,然后就可以对不同大小的距离进行计数,假如相同的距离x一共有t个,那么以该点为中心的边长为x的回旋就有A2t个,也就是t*(t-1)个。把以每个点为中心的回旋数加起来就是答案。

代码

#include<stdio.h>
#include<algorithm>
using std::sort;
int x[1005];
int y[1005];

int d[1005][1005];
int main() {
    int kase,n;
    scanf("%d", &kase);
    for (int t = 0; t < kase; ++t)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d %d", &x[i], &y[i]);
        //计算距离矩阵
        for (int i = 0; i < n; ++i)
        {
            for (int j = i; j < n; ++j)
                d[i][j] = d[j][i] = (x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]);
        }

        //每个点的距离数组分别排序
        for (int i = 0; i < n; ++i) 
            sort(d[i], d[i] +n );


        int ans = 0,temp=1;
        for (int i = 0; i < n; ++i) {
            temp = 1;
            //对距离计数
            for (int j = 1; j < n; ++j) {
                if (d[i][j] == d[i][j - 1])//如果相同则temp++
                temp++;
                else {//如果不同,说明之前相同的距离已经计数完毕
                    ans += temp*(temp - 1);
                    temp = 1;
                }
            }
            ans += temp*(temp - 1);
        }
        if (ans == 0)printf("WA\n");
        else printf("%d\n",ans);
    }
}

总结

解空间就是,要统计到一个点距离相同的点数,把点的记录转化为距离的记录,降低了维数,也让记录更为直观。

相关标签: 组合