本文共 1569 字，大约阅读时间需要 5 分钟。

题目

“一闪一闪亮晶晶，满天都是小星星”

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

输出样例

YES5 6 7 81 2 3 4

解

用循环模拟判断各种情况容易出错。所以我们用DFS暴力枚举点的关系，用四边的长与对角线判断四边形形状。

代码

#include
   
    #include
    
     #include
     
      using namespace std;bool B[10];int f[10][10],Q[10],x[10],y[10],pd;void dfs(int deep){    if(deep > 4)  //前四个能否构成正方形   if(f[Q[1]][Q[2]] != f[Q[3]][Q[4]] || f[Q[1]][Q[4]] != f[Q[2]][Q[3]] || f[Q[1]][Q[2]] != f[Q[1]][Q[4]] || f[Q[1]][Q[3]] != f[Q[2]][Q[4]])   //四边相等+对角线相等=正方形     return; if(deep > 8) {     if(f[Q[5]][Q[6]] != f[Q[7]][Q[8]] || f[Q[5]][Q[8]] != f[Q[6]][Q[7]] || f[Q[5]][Q[7]] != f[Q[6]][Q[8]])   //对边相等+对角线相等=矩形return;  pd = 1;  //找到结果  sort(Q+1,Q+5); //排序  sort(Q+6,Q+9);  return; } for(int i = 1; i <= 8; ++i)   if(B[i] == 0){         B[i] = 1;      Q[deep] = i;  //储存枚举结果      dfs(deep+1);      if(pd == 1) return;      B[i] = 0;   }}int main(){    for(int i = 1; i <= 8; ++i){     scanf("%d%d", &x[i], &y[i]);  for(int j = 1; j < i; ++j)    f[i][j] = f[j][i] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);    //用勾股定理提前处理两点间的距离    //不开平房是因为开完之后概率出现误差 } dfs(1); if(pd == 0) printf("NO"); else{     printf("YES\n");  //输出  for(int i = 1; i <= 4; ++i)    printf("%d ",Q[i]);  printf("\n");  for(int i = 5; i <= 8; ++i)    printf("%d ",Q[i]); }}