题目难度：三星
考察点：计算几何

方法：计算几何、枚举

  1. 分析：
    对于这道题来说我们有如下需要考虑的地方：
    (1). 一个点A(x1,y1)围绕一个点B(x2,y2)逆时针旋转90°一次，对应坐标A的变化？旋转多次呢？
    我们都知道如果B是原点的话，那么逆时针旋转90°一次之后坐标A(x1,y1)将变为C(y1, x1)，那么如果B不是原点呢？我们将整个坐标系进行移动，将B移动到原点，那么A的坐标就会变为(x1-x2,y1-y2)，那么此时进行逆时针旋转90°，A的坐标就会变为C(y1-y2,x1-x2)。注意，此时C的坐标是相对于B点来说的，如果相对于原点来说的话，就变成D(y1-y2+x2,x1-x2+y2)，那么总结一下:就是点A(x1,y1)围绕一个点B(x2,y2)逆时针旋转90°一次之后的坐标变为D(y1-y2+x2,x1-x2+y2)。如果旋转多次的话，就把A点变为D，继续循环下去（最多旋转3次，因为旋转4次就相当于没有旋转）
    (2). 如何判断4个点是否能够构成正方形？
    我们只要获取4条边的边长，如果4条边相等且不为0，同时满足有一个角是直角，那么这4个点就能够构成正方形。首先我们将这4个点按照x坐标排序，如果x坐标相同按照纵坐标排序（都是从小到大排序）。那么排完序之后的坐标记作p0,p1,p2,p3，那么4条边的边长分别为p0p1, p0p2 p1p3, p2p3，判断一个角是否为直角，可以判断它们的点乘是否为0，如果为0证明是直角，否则不是直角.
    (3). 如何计算移动最少次数使得四个点构成正方形呢？
    我们可以进行枚举，一共有4个点，每个点可以旋转4次，一共是4^4种方法，我们将这些方法全部枚举出来，获得最小值就好了。

算法实现：
(1).首先进行枚举，4个变量i,j,k,l分别表示4个点的旋转次数，那么移动次数就等于i+j+k+l
(2).对于旋转之后的4个点，我们判断是否能够组成正方形即可，判断是否为正方形的方法已经在上面叙述了。
(3). 输出最小移动次数。

  1. 复杂度分析：
    时间复杂度：O(4^4*n)
    空间复杂度：O(1)

  2. 代码：

    #include <bits/stdc++.h>
using namespace std;
struct Point {
 int x, y;
};
bool cmp(Point A, Point B) {
 if(A.x == B.x) return A.y < B.y;
 return A.x < B.x;
}
int Dis2(Point A, Point B) {
 return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}
//AB⊥BC
bool isRightAngle(Point A, Point B, Point C) {
 int x = (B.x-A.x)*(C.x-B.x);
 int y = (B.y-A.y)*(C.y-B.y);
 return x+y==0;
}
bool isSqure(Point p[4]) {
 sort(p, p+4, cmp);
 int dis[4];
 dis[0] = Dis2(p[0], p[1]);
 dis[1] = Dis2(p[0], p[2]);
 dis[2] = Dis2(p[1], p[3]);
 dis[3] = Dis2(p[2], p[3]);
 sort(dis, dis+4);
 if(dis[0]==dis[3] && dis[0] && isRightAngle(p[1], p[0], p[2])) return true;
 return false;
}
Point rotate(Point A, Point B, int t) {
 Point tmp;
 for(int i=0; i<t; i++) {
     tmp.x = B.x - A.y + B.y;
     tmp.y = A.x - B.x + B.y;
     A = tmp;
 }
 return A;
}
Point a[4], b[4], p[4];
int main() {
 int n; cin>>n;
 while(n--) {
     for(int i=0; i<4; i++) cin>>a[i].x>>a[i].y>>b[i].x>>b[i].y;
     int ans = 20;
     for(int i=0; i<4; i++) {
         for(int j=0; j<4; j++) {
             for(int k=0; k<4; k++) {
                 for(int l=0; l<4; l++) {
                     p[0] = rotate(a[0], b[0], i);
                     p[1] = rotate(a[1], b[1], j);
                     p[2] = rotate(a[2], b[2], k);
                     p[3] = rotate(a[3], b[3], l);
                     if(isSqure(p)) ans = min(ans, i+j+k+l);
                 }
             }
         }
     }
     if(ans == 20) ans = -1;
     cout<<ans<<endl;
 }
 return 0;
}

```