KC看星

本文主要是介绍KC看星，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
“一闪一闪亮晶晶，满天都是小星星”

Kc吟唱着歌谣，躺在草坪上边想着她边看起了星星。Kc刚刚结识了笛卡尔这位好基友，认为他的坐标系非常神奇。于是他随机地选出了8颗星星，并且给它们标上了坐标。Kc又不甘寂寞，于是思考起一个问题：这八个点能否恰好构成一个正方形和一个矩形呢？

输入
输入文件包括1行16个数，表示8个星星的坐标，坐标绝对值不超过10000。
输出
输出文件第一行是"YES"或者"NO"。表示是否有解。

若有解则第二行依次输出正方形每个顶点的序号。第三行依次输出矩形每个顶点的序号。序号即为输入的顺序。

另外注意：因为kc是一个刁端的人，所以他要求第二行和第三行这八个数要字典序最小。

四点共线不能认为是正方形或矩形
输入样例
0 0 10 11 10 0 0 11 1 1 2 2 2 1 1 2

输出样例
YES
5 6 7 8
1 2 3 4

.
.
.
.
.
.
分析
先全排列出序列，再用图形定理判断即可

.
.
.
.
.
程序：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;int b[10];
bool v[10];
double d[10][10];struct ajsdofno
{int x,y;
}a[10];void check()
{bool bz1=false,bz2=false;if (d[b[1]][b[2]]!=0&&d[b[1]][b[2]]==d[b[3]][b[4]]&&d[b[1]][b[3]]==d[b[2]][b[4]]&&d[b[1]][b[2]]==d[b[1]][b[3]]&&d[b[1]][b[4]]!=0&&d[b[1]][b[4]]==d[b[2]][b[3]]) bz1=true;if (d[b[5]][b[6]]!=0&&d[b[5]][b[6]]==d[b[7]][b[8]]&&d[b[5]][b[8]]!=0&&d[b[5]][b[8]]==d[b[6]][b[7]]&&d[b[5]][b[7]]!=0&&d[b[5]][b[7]]==d[b[6]][b[8]])  bz2=true;if (bz1&&bz2){sort(b+1,b+4+1);sort(b+5+1,b+8+1);printf("YES\n");for (int i=1;i<=4;i++)printf("%d ",b[i]);printf("\n");for (int i=5;i<=8;i++)printf("%d ",b[i]);exit(0);}
}void dfs(int wz)
{if (wz>8){check();return;}for (int i=1;i<=8;i++)if (!v[i]){v[i]=true;b[wz]=i;dfs(wz+1);v[i]=false;}
}int main()
{for (int i=1;i<=8;i++)scanf("%d%d",&a[i].x,&a[i].y);for (int i=1;i<=8;i++)for (int j=1;j<=8;j++)if (i!=j) d[i][j]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));memset(v,false,sizeof(v));dfs(1);printf("NO");return 0;
}

这篇关于KC看星的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---