[编程题]整理房间
• 热度指数：5538 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
• 算法知识视频讲解

##### 输入描述:
`第一行一个数n(1 <= n <= 100)，表示杂物的团数。接下来4n行，每4行表示一团杂物，每行4个数ai, bi，xi, yi, (-104 <= xi, yi, ai, bi <= 104)，表示第i个物品旋转的它本身的坐标和中心点坐标。`

##### 输出描述:
`n行，每行1个数，表示最少移动次数。`

```4
1 1 0 0
-1 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-2 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-1 1 0 0
-1 1 0 0
-1 1 0 0
2 2 0 1
-1 0 0 -2
3 0 0 -2
-1 1 -2 0```

```1
-1
3
3```

## 说明

`对于第一团杂物，我们可以旋转第二个或者第三个物品1次。`
```import java.util.Scanner;

class Point {
int x1;
int y1;
int x;
int y;

Point(int x1, int y1, int x, int y) {
this.x1 = x1;
this.y1 = y1;
this.x = x;
this.y = y;
}
}

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Point[][] points = new Point[n][4];
int a, b, c, d;
int[] reult = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
a = sc.nextInt();
b = sc.nextInt();
c = sc.nextInt();
d = sc.nextInt();
points[i][j] = new Point(a, b, c, d);
}
reult[i] = moveIimes(points, i);
}
for (int i = 0; i < reult.length; i++) {
System.out.println(reult[i]);
}
}

//每个点有4中情况旋转0，1,2,3次，穷举
private static int moveIimes(Point[][] pints, int i) {
Point p1, p2, p3, p4;
int count = 16;
for (int j = 0; j < 4; j++) {
//第一个点的
p1 = rotate(pints[i][0], j);
for (int k = 0; k < 4; k++) {
p2 = rotate(pints[i][1], k);
for (int l = 0; l < 4; l++) {
p3 = rotate(pints[i][2], l);
for (int m = 0; m < 4; m++) {
p4 = rotate(pints[i][3], m);
if (isSq(p1, p2, p3, p4)) {
count = Math.min(count, j + k + l + m);
}
}
}
}
}
return count == 16 ? -1 : count;
}

/**
* @param p     原始点
* @param times 旋转次数
* @return 返回旋转后的点
*/
private static Point rotate(Point p, int times) {
int x = p.x1;
int y = p.y1;
int a = p.x;//中心点
int b = p.y;
for (int i = 1; i <= times; i++) {
int tem = x;
x = (b - y + a);
y = (tem - a + b);
}
return new Point(x, y, a, b);
}

//判断四个点是否是正方形
private static boolean isSq(Point p1, Point p2, Point p3, Point p4) {
boolean rx = ((p1.x1) ^ (p2.x1) ^ (p3.x1) ^ (p4.x1)) == 0;//四个点的 x 坐标是否是两两相等
boolean ry = ((p1.y1) ^ (p2.y1) ^ (p3.y1) ^ (p4.y1)) == 0;//四个点的 y 坐标是否是两两相等
//是否是矩形
if (!rx || !ry || rx && ry && (p1.x1 == p2.x1 && p1.x1 == p3.x1) ||
rx && ry && (p1.y1 == p2.y1 && p1.y1 == p3.y1)) return false;
//判断正方形
int dx = Math.abs((p1.x1 - p2.x1) != 0 ? (p1.x1 - p2.x1) : (p1.x1 - p3.x1));
int dy = Math.abs((p1.y1 - p2.y1) != 0 ? (p1.y1 - p2.y1) : (p1.y1 - p3.y1));
return dx == dy;
}

}
```

```import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();

int[][][] abxy=new int[n][4][4];
for(int i=0;i<n;i++){
for(int j=0;j<4;j++){
abxy[i][j][0]=sc.nextInt();
abxy[i][j][1]=sc.nextInt();
abxy[i][j][2]=sc.nextInt();
abxy[i][j][3]=sc.nextInt();
}
}
for(int index=0;index<n;index++){
int min=Integer.MAX_VALUE;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int m=0;m<4;m++){
if(isSquare(rotate(abxy[index][0],i),rotate(abxy[index][1],j),rotate(abxy[index][2],k),rotate(abxy[index][3],m))){
min=Math.min(min,i+j+k+m);
}
}
}
}
}
if(min==Integer.MAX_VALUE){
min=-1;
}
System.out.println(min);
}

}
//绕xy旋转count次 point长度为4，固定这个长度是因为这样在调用的时候比较方便
public static  int[] rotate(int[] point,int count){
int[] res=new int[] {point[2]+point[3]-point[1], point[3]-point[2]+point[0],point[2],point[3]};
if(count==0){
return point;
}else{
return rotate(res,count-1);
}
}
//判定正方形，一定要判定两个对角边是否相等
public static  boolean isSquare(int[] point1,int[] point2,int[] point3,int[] point4){
double[] sideLen=new double[]{distance(point1,point2),distance(point2,point3),distance(point3,point4),distance(point4,point1),distance(point1,point3),distance(point2,point4)};
Arrays.sort(sideLen);
return sideLen[0] != 0&&sideLen[0]==sideLen[1]&&sideLen[1]==sideLen[2]&&sideLen[2]==sideLen[3]&&sideLen[3]==sideLen[0]
&&sideLen[4]==sideLen[5];
}

private static double distance(int[] fromPoint, int[] toPoint) {
return Math.pow(fromPoint[0] - toPoint[0], 2)
+ Math.pow(fromPoint[1] - toPoint[1], 2);
}
}
```

``````#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <limits.h>
#include <cstdio>
using namespace std;

struct Item{
int a, b, x, y, state;
Item(){
state = 0;
}

void crot(){
state = (state + 1) % 4;
int dx = a-x, dy = b-y;
a = x - dy;
b = y + dx;
}

void input(){
cin>>a>>b>>x>>y;
state = 0;
}

bool operator ==(const Item &item2){
return a==item2.a && b==item2.b;
}

Item operator +(const Item &it2){
Item res;
res.a = a + it2.a;
res.b = b + it2.b;
return res;
}

Item operator -(const Item &it2){
Item res;
res.a = a - it2.a;
res.b = b - it2.b;
return res;
}

static bool ortho(const Item &it1, const Item &it2){
if(it1.a==0 && it1.b== 0) return 0;
if(it2.a==0 && it2.b == 0) return 0;
return it1.a * it2.a + it1.b * it2.b == 0;
}
};

struct Pack{
vector<Item> itemList;
vector<Item*> itp;
int step;

Pack(){
itemList = vector<Item>(4);
itp = vector<Item*>(4, nullptr);
for(int i=0; i<4; ++i) itp[i] = &itemList[i];
step = INT_MAX;
}

void input(){
for(int i=0; i<4;++i)
itemList[i].input();
step = INT_MAX;
}

bool isSqaure(){
for(int i=1; i<4; ++i){
if(i!=1) swap(itp[i], itp[1]);
if(*itp[0]==*itp[1] || *itp[2]==*itp[3]) return 0;
if(!(*itp[0] + *itp[1] == *itp[2] + *itp[3])) continue;
if(!Item::ortho(*itp[0]- *itp[1], *itp[2] - *itp[3])) continue;
if(Item::ortho(*itp[0]- *itp[2], *itp[0] - *itp[3])) return 1;
}
return 0;
}

void trySqaure(int rot_idx){
for(int i=0; i<4; ++i){
if(rot_idx == 0 && isSqaure()){
int tmp_step = 0;
for(int j=0; j<4; ++j) tmp_step += itemList[j].state;
if(step > tmp_step) step = tmp_step;
}
if(rot_idx > 0) trySqaure(rot_idx - 1);
itemList[rot_idx].crot();
}
}
};

int main()
{
int n;
cin>>n;
Pack eRoom;
for(int i=0; i<n; ++i){
eRoom.input();
eRoom.trySqaure(3);
cout<<(eRoom.step > 16 ? -1: eRoom.step)<<endl;
}
}
``````

1. 如何判断四个点能否组成正方形: 假设四个点编号为[1, 2, 3, 4], 考虑正方形的对称性, 检查i) 1->2->3->4, ii) 1->3->2->4, iii) 1->2->4->3 这三种情况能否组成正方形即可. 确定顺序后四条边边长相等且对角线长度相等即可组成正方形.
2. 如何绕将点p绕点c逆时针旋转90度: i) 将坐标原点移动至点c: p.x -= c.x, p.y -= c.y ii) 绕坐标原点逆时针旋转90度: p.x = -p.y, p.y=p.x. 可用极坐标证明上式. iii) 将坐标原点重新移回(0, 0): p.x += c.x, p.y += c.y
3. 如何确定最小操作次数: 4团杂物每个有4种旋转情况, 将4^4 = 256种组合情况均枚举一遍即可.
```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Point{
public:
int x, y;
Point()=default;
Point(int x, int y): x(x), y(y) {};

bool operator== (const Point &a) const {
return x == a.x && y == a.y;
}

void rotate(const Point &center) {
x -= center.x;
y -= center.y;
swap(x, y);
x = -x;
x += center.x;
y += center.y;
return;
}
};

int distance(const Point &a, const Point &b) {
return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}

bool is_square(const Point &a, const Point &b, const Point &c, const Point &d) {
if(a == b || a == c || a == d || b == c || b == d || c == d)
return false;

// 1 2 3 4
if(distance(a, b) == distance(b, c) && distance(b, c) == distance(c, d) &&
distance(c, d) == distance(d, a) && distance(a, c) == distance(b, d))
return true;

// 1 2 4 3
if(distance(a, b) == distance(b, d) && distance(b, d) == distance(d, c) &&
distance(d, c) == distance(c, a) && distance(a, d) == distance(b, c))
return true;

// 1 4 2 3
if(distance(a, d) == distance(d, b) && distance(d, b) == distance(b, c) &&
distance(b, c) == distance(c, a) && distance(a, b) == distance(c, d))
return true;

return false;
}

void backtrack(const vector<Point> &points, const vector<Point> &centers, int pos, vector<Point> &curr, int ops, int &res) {
if(curr.size() == 4) {
if(is_square(curr[0], curr[1], curr[2], curr[3]))
res = res == -1 ? ops : min(res, ops);
return;
}

int local_op = 0, k = 0;
auto p = points[pos];
do {
curr.push_back(p);
backtrack(points, centers, pos+1, curr, ops+local_op, res);
curr.pop_back();

p.rotate(centers[pos]);
local_op++;
k++;
} while(k < 4);

return;
}

int main() {
int n;
cin >> n;
int px, py, cx, cy;
vector<Point> points(4), centers(4);
for(int i = 0; i < n; i++) {
for(int k = 0; k < 4; k++) {
cin >> px >> py >> cx >> cy;
points[k] = Point(px, py);
centers[k] = Point(cx, cy);
}
int res = -1;
vector<Point> curr;
backtrack(points, centers, 0, curr, 0, res);
cout << res << endl;
}

return 0;
}```

```// 穷举
// 逆时针转四次就转回去了,所以每次直接修改原数组就可以了,不用定义另外的class
// 一定要注意计算距离的时候用long, 否则要溢出(算平方就行,不用开根号,所以没用double,于是遇到了溢出)
// 判断是否是正方形: 最短边有4条,最长边有2条
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
int[][] points = new int[4][4];
String[] strs;
while(n-- >0){
int cnt = Integer.MAX_VALUE;
for(int i = 0; i < 4; i++){
points[i][0] = Integer.parseInt(strs[0]);
points[i][1] = Integer.parseInt(strs[1]);
points[i][2] = Integer.parseInt(strs[2]);
points[i][3] = Integer.parseInt(strs[3]);
}

for(int i = 0; i < 4; i++){
rotateCounterClockwise(points[0]);
for(int j = 0; j < 4; j++){
rotateCounterClockwise(points[1]);
for(int k = 0; k < 4; k++){
rotateCounterClockwise(points[2]);
for(int l = 0; l < 4; l++){
rotateCounterClockwise(points[3]);
if(isSquare(points)){
int c = (i+1)%4+(j+1)%4+(k+1)%4+(l+1)%4;
if(c < cnt) cnt = c;
}
}
}
}
}
System.out.println(cnt == Integer.MAX_VALUE ? -1 : cnt);
}
br.close();
}

// 逆时针转一次
private static void rotateCounterClockwise(int[] point){
int x = point[0];
point[0] = point[2] + point[3] - point[1];
point[1] = x - point[2] + point[3];
}

private static boolean isSquare(int[][] points){
long min = Long.MAX_VALUE, max = Long.MIN_VALUE;
int cnt1 = 0, cnt2 = 0;
long tmp = 0;
for(int i = 0; i < 3; i++){
for(int j = i+1; j < 4; j++){
tmp = distance(points,i,j);
if(tmp < min){min = tmp; cnt1 = 1;}
else if(tmp == min) {cnt1++;}
if(tmp > max){max = tmp; cnt2 = 1;}
else if(tmp == max) {cnt2++;}
}
}
return cnt1 == 4 && min != 0 && cnt2 == 2;
}

private static long distance(int[][] points, int i, int j){
return ((long)(points[i][0] - points[j][0]))*(points[i][0] - points[j][0])
+ (points[i][1] - points[j][1])*(points[i][1] - points[j][1]);
}

}```

 ```defchange(i, x, y):     return[x +y -i[1], y -x +i[0]] defdis(a, b):     return(a[0] -b[0])**2+(a[1] -b[1])**2 defsquare(a, b, c, d):     q =[dis(a, b), dis(a, c), dis(a, d), dis(b, c), dis(b, d), dis(c, d)]     q.sort()     ifq[0]!=0andq[0] ==q[1] andq[1] ==q[2] andq[2] ==q[3] andq[4] ==q[5]andq[4] ==2*q[3]:         returnTrue     returnFalse   n =int(raw_input().strip()) forw inrange(n):     best =100     p =[]     fori inrange(4):         a, b, x, y =map(int, raw_input().strip().split())         temp1 =[[a, b]]         forj inrange(3):             temp1.append(change(temp1[-1], x, y))         p.append(temp1)           fori inrange(4):         forj inrange(4):             fork inrange(4):                 forl inrange(4):                     ifsquare(p[0][i], p[1][j], p[2][k], p[3][l]):                         best =min(best, i +j +k +l)     ifbest ==100:         best =-1     printbest```

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] nums = new int[4][4];
for (int i = 0; i < n; i++){
for (int j = 0; j < 4; j++){
for (int k = 0; k < 4; k++){
nums[j][k] = sc.nextInt();
}
}
int result = findMinMoveTimes(nums);
if (result == Integer.MAX_VALUE)
result = -1;
System.out.println(result);
}
}

private static int findMinMoveTimes(int[][] nums) {
int i = 0;
int j = 0;
int k = 0;
int z = 0;
int minTimes = Integer.MAX_VALUE;
boolean flag = false;
for (i = 0; i < 4; i++){
if (flag){
rotate(nums, 0);
}
for (j = 0; j < 4; j++){
if (flag){
rotate(nums, 1);
}
for (k = 0; k < 4; k++){
if (flag){
rotate(nums, 2);
}
for (z = 0; z < 4; z++){
if (flag){
rotate(nums, 3);
}else {
flag = true;
}
if (isSquare(nums[0], nums[1], nums[2], nums[3])){
int times = i + j + k + z;
if (times < minTimes){
minTimes = times;
}
}
}

}
}
}
return minTimes;
}

private static void rotate(int[][] nums, int index) {
int[] num = nums[index];
int oldx = num[0];
int oldy = num[1];
int centerx = num[2];
int centery = num[3];
nums[index][0] = centerx + centery - oldy;
nums[index][1] = centery - centerx + oldx;
}

private static boolean isSquare(int[] neePoint1, int[] neePoint2, int[] neePoint3, int[] neePoint4){
long[] dis = new long[6];
dis[0] = dis(neePoint1, neePoint2);
dis[1] = dis(neePoint1, neePoint3);
dis[2] = dis(neePoint1, neePoint4);
dis[3] = dis(neePoint2, neePoint3);
dis[4] = dis(neePoint2, neePoint4);
dis[5] = dis(neePoint3, neePoint4);
int count = 0;
long minDis = Long.MAX_VALUE;
for (int i = 0; i < 6; i++){
if (dis[i] < minDis){
minDis = dis[i];
}
}
for (int i = 0; i < 6; i++){
if (dis[i] == minDis){
count++;
}
}
return count == 4;
}

private static long dis(int[] neePoint1, int[] neePoint2) {
long x = neePoint1[0] - neePoint2[0];
long y = neePoint1[1] - neePoint2[1];
return (x * x + y * y);
}

}

```#include<bits/stdc++.h>
using namespace std;
int X[4][4],Y[4][4];//分别存放四个点逆时针旋转的横坐标和纵坐标
map<int,int>mp;//判断四个点围成的是否是正方形
bool judge(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
mp.clear();
mp[(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)]++;
mp[pow((x1-x3),2)+pow((y1-y3),2)]++;
mp[pow((x1-x4),2)+pow((y1-y4),2)]++;
mp[pow((x2-x3),2)+pow((y2-y3),2)]++;
mp[pow((x2-x4),2)+pow((y2-y4),2)]++;
mp[pow((x3-x4),2)+pow((y3-y4),2)]++;
if(mp.size()==2&&!mp.count(0))return 1;//当mp元素是两个并且没有0元素为真，因为可能会有相同坐标出现
return 0;
}
int ans = 1000000;
for(int i = 0;i<4;i++){//枚举四个点所有旋转过的坐标判断是否是正方形，更新答案
for(int j = 0;j<4;j++){
for(int m = 0;m<4;m++){
for(int n = 0;n<4;n++){
if(judge(x[0][i],y[0][i],x[1][j],y[1][j],x[2][m],y[2][m],x[3][n],y[3][n])){
ans = min(ans,i+j+m+n);
cout<<ans<<endl;
}
}
}
}
}
return ans;
}
int main(){
int n;
cin>>n;
while(n--){
for(int i = 0;i<4;i++){
int x,y,a,b;
cin>>x>>y>>a>>b;
X[i][0] = x,Y[i][0] = y;//以下四行是求每个点逆时针旋转的横纵坐标
X[i][1] = a-(y-b),Y[i][1] = b+(x-a);
X[i][2] = a-(Y[i][1]-b),Y[i][2] = b+(X[i][1]-a);
X[i][3] = a-(Y[i][2]-b),Y[i][3] = b+(X[i][2]-a);
}
if(ans==1000000)cout<<-1<<endl;
else cout<<ans<<endl;
}
return 0;
}
```

```import java.io.*;

// 创建一个 Point 类
class Point {
int a;
int b;
int x;
int y;

public Point(int a, int b, int x, int y) {
this.a = a;
this.b = b;
this.x = x;
this.y = y;
}
}

public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
Point[] p = new Point[4]; // 用 p 来存放四个点
for (int j = 0; j < 4; j++) {
p[j] = new Point(Integer.parseInt(line[0]),
Integer.parseInt(line[1]),
Integer.parseInt(line[2]),
Integer.parseInt(line[3]));
}
sb.append(minMove(p)).append("\n");
}
System.out.print(sb);
br.close(); // 关闭 io
}

public static int minMove(Point[] p) {
int move = 16;
for (int i = 1; i <= 4; i++) {
rotate(p[0]);
for (int j = 1; j <= 4; j++) {
rotate(p[1]);
for (int k = 1; k <= 4; k++) {
rotate(p[2]);
for (int v = 1; v <= 4; v++) {
rotate(p[3]);
if (isSquare(p)) {
move = Math.min(move, i%4 + j%4 + k%4 + v%4);
}
}
}
}
}
return move == 16 ? -1 : move;
}

// 原地修改
public static void rotate(Point point) {
int tmp = point.a;
point.a = point.x + point.y - point.b;
point.b = point.y - point.x + tmp;
}

// 找最长的边长和最短的边长，前者出现两次，后者出现四次且不为 0 ，则正方形成立
public static boolean isSquare(Point[] p) {
long min = Long.MAX_VALUE, max = Long.MIN_VALUE;
int count1 = 0, count2 = 0;
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 4; j++) {
long dis = distance(p[i], p[j]);
if (dis > max) { max = dis; count1 = 1; }
else if (dis == max) count1++;
if (dis < min) { min = dis; count2 = 1; }
else if (dis == min) count2++;
}
}
return count1 == 2 && count2 == 4 && min != 0;
}
// 注意使用 long 类型防止溢出
public static long distance(Point p1, Point p2) {
return ((long) (p1.a - p2.a) * (p1.a - p2.a)
+ (p1.b - p2.b) * (p1.b - p2.b));
}
}```

JavaScript(Node) 😎题目:网易-整理房间（穷举）
```const readline = require('readline');
const lines = [];
input: process.stdin,
output: process.stdout
});
let n = -1;
let pos1, pos2, pos3, pos4;
rl.on('line', function(line) {
lines.push(line.split(" ").map(i => Number(i)));
if(lines.length === 1) {
n = Number(lines[0][0]);
}
if(lines.length === 4*n+1) {
for(let i=0; i<n; i++) {
pos1 = lines[4*i+1];
pos2 = lines[4*i+2];
pos3 = lines[4*i+3];
pos4 = lines[4*i+4];
console.log(move(pos1, pos2, pos3, pos4));
}
}
});
function move(pos1, pos2, pos3, pos4){
let count = 16;
let p1, p2, p3, p4;
for(let j=0;j<4;j++) {
p1 = rotate(pos1, j);
for(let k=0;k<4;k++) {
p2 = rotate(pos2, k);
for(let l=0;l<4;l++) {
p3 = rotate(pos3, l);
for(let m=0;m<4;m++) {
p4 = rotate(pos4, m);
if(isSquare(p1, p2, p3, p4)) {
count = Math.min(count, j+k+l+m);
}
}
}
}
}
return count === 16 ? -1 : count;
}
function rotate(pos, times) {
var [a, b, x, y] = pos;
for(let i=1;i<=times;i++) {
var temp = a;
a = y-b+x;
b = temp-x+y;
}
// (a-x, b-y) => (y-b, a-x)
return [a, b, x, y];
}
function distance(pos1, pos2) {
return Math.pow(pos1[0]-pos2[0], 2) + Math.pow(pos1[1]-pos2[1], 2);
}
function isSquare(pos1, pos2, pos3, pos4) {
var q = [distance(pos1, pos2), distance(pos1, pos3), distance(pos1, pos4), distance(pos2, pos3), distance(pos2, pos4), distance(pos3, pos4)];
q.sort((a, b) => a-b);
if(q[0] !== 0 && q[0]===q[1] && q[1]===q[2] && q[2]===q[3] && q[4]===q[5] && q[4]===2*q[3]) {
return true;
}
return false;
}```

```#include <bits/stdc++.h>
using namespace std;
int cnt;
class P{
public:
int x,y;
P(){};
P(int x, int y):x(x),y(y){};
void R(P c){
int dx = x - c.x;
int dy = y - c.y;
x = c.x - dy;
y = c.y + dx;
return;
}
};

double Dist(P p1, P p2){
return sqrt(pow(p1.x-p2.x,2) + pow(p1.y-p2.y,2));
}

bool F(vector<P> p){
double d[6];
for(int i=0,k=0;i<4;i++)
for(int j=i+1;j<4;j++)
d[k++] = Dist(p[i], p[j]);
sort(d, d+6);
if(d[0]!=0 && d[0]==d[1] && d[0]==d[2] && d[0]==d[3] && d[4]==d[5])
return true;
return false;
}

void DFS(P *p, P *c, vector<P> &r, int k, int s){
if(r.size()==4){
if(F(r))
cnt = min(cnt, s);
return;
}
int t=0;
P q = p[k];
for(int i=0;i<4;i++){
r.push_back(q);
DFS(p, c, r, k+1, s+t);
r.pop_back();
q.R(c[k]);
t++;
}
return ;
}

int main(){
int n;
cin>>n;
int a,b,x,y;
P p[4],c[4];
for(int i=0;i<n;i++){
for(int j=0;j<4;j++){
cin>>a>>b>>x>>y;
p[j] = P(a, b);
c[j] = P(x, y);
}
cnt = INT_MAX;
vector<P> r;
DFS(p, c, r, 0, 0);
cout<<((cnt==INT_MAX)?-1:cnt)<<endl;
}
return 0;
}```

## 笛卡尔坐标系内点旋转公式：
(a,b)为旋转中心，（x,y）为旋转初始点，(x',y')为旋转目标点

θ 是逆时针的旋转角
x' = xcosθ  - ysinθ  + a(1-cosθ ) + bsinθ
y' = xsinθ  + ycosθ  + a(-sinθ ) + b(1-cosθ)

x' =  -y + a + b
y' = x -a + b

## 如何判断四个点能否构成正方形
判断方法如下：
若有3个点的x相等或3个点的y相等，直接为false
选定1个点p1, 则其余3个点分别为：p2,p3,p4
始终以p1作为要判断的角的顶点，则有如下几种可能：
p1与p2对角，p1p3 = p1p4=p2p3=p2p4，且p3p1p4为直角
p1与p3对角，p1p2 = p1p4=p3p2=p3p4，且p2p1p4为直角
p1与p4对角，p1p2 = p1p3=p4p2=p4p3，且p2p1p3为直角

1.距离：

2.角度

bool IsRightAngle(int x1,int y1,int x2,int y2,int x3,int y3){
if((x2-x1)* (x3-x1)+(y2-y1)* (y3-y1)==0)
return true;
return false;
}

```import java.util.Scanner;

public class Main {
static class Point{
int x;
int y;

Point(int x, int y){
this.x = x;
this.y = y;
}
//返回该点与点p之间距离的的平方
int squareOfDistance(Point p){
return (p.x-x)*(p.x-x) + (p.y-y)*(p.y-y);
}
}

static class PointGroup{
Point pivot; //轴点
Point main;  //主点

PointGroup(Point m, Point p){
main = m;
pivot = p;
}

}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();

//每4个点是一组
PointGroup[][] points = new PointGroup[n][4];
for(int i=0;i<n;i++){
for(int j=0;j<4;j++){
Point m = new Point(in.nextInt(), in.nextInt());
Point p = new Point(in.nextInt(),in.nextInt());
points[i][j] = new PointGroup(m, p);
}
}

int[] ans = new int[n];
for(int i=0;i<n;i++){
Point p1,p2,p3,p4;

int minStep = Integer.MAX_VALUE;
for(int i1=0;i1<4;i1++){
p1 = rotate(points[i][0].main, points[i][0].pivot, i1);
for(int i2=0;i2<4;i2++){
p2 = rotate(points[i][1].main, points[i][1].pivot, i2);
for(int i3=0;i3<4;i3++){
p3 = rotate(points[i][2].main, points[i][2].pivot, i3);
for(int i4=0;i4<4;i4++){
p4 = rotate(points[i][3].main, points[i][3].pivot, i4);
if(isSquare(p1,p2,p3,p4)){
minStep = Math.min(minStep, i1+i2+i3+i4);
}
}
}
}
}
if(minStep==Integer.MAX_VALUE) ans[i]=-1;
else ans[i]=minStep;
}

for(int i=0;i<n;i++){
System.out.println(ans[i]);
}

}

//将p绕pivot旋转count个90度后的点返回
public static Point rotate(Point p, Point pivot, int count){
Point ans = new Point(p.x, p.y);
Point pre = new Point(p.x, p.y);
for(int i=0;i<count;i++){
ans.x = -pre.y+pivot.x+pivot.y;
ans.y = pre.x - pivot.x + pivot.y;
pre.x = ans.x;
pre.y = ans.y;
}
return ans;
}

public static boolean isRightAngle(Point p1, Point p2, Point p3){
if((p2.x-p1.x)* (p3.x-p1.x)+(p2.y-p1.y)* (p3.y-p1.y)==0)
return true;
return false;
}

//判断四个点能否构成正方形
public static boolean isSquare(Point p1, Point p2, Point p3, Point p4){
//若有三个点x或y相等，直接返回false
if((p1.x==p2.x && p1.x==p3.x) || (p1.x==p2.x && p1.x==p4.x) || (p1.x==p3.x && p4.x==p3.x)|| (p2.x==p3.x && p4.x==p3.x)
|| (p1.y==p2.y && p1.y==p3.y) || (p1.y==p2.y && p1.y==p4.y) || (p1.y==p3.y && p4.y==p3.y)|| (p2.y==p3.y && p4.y==p3.y)){
return false;
}
//若始终以p1作为要判断的角的顶点，则有如下几种可能：
/*
p1与p2对角，p1p3 = p1p4=p2p3=p2p4，且p3p1p4为直角
p1与p3对角，p1p2 = p1p4=p3p2=p3p4，且p2p1p4为直角
p1与p4对角，p1p2 = p1p3=p4p2=p4p3，且p2p1p3为直角
*/
if(p1.squareOfDistance(p3)==p1.squareOfDistance(p4) && p2.squareOfDistance(p3)==p2.squareOfDistance(p4) && p1.squareOfDistance(p4) == p2.squareOfDistance(p3)){
if(isRightAngle(p1,p3,p4)) return true;
else return false;
}

if(p1.squareOfDistance(p2)==p1.squareOfDistance(p4) && p3.squareOfDistance(p2)==p3.squareOfDistance(p4) && p1.squareOfDistance(p2) == p3.squareOfDistance(p2)){
if(isRightAngle(p1,p2,p4)) return true;
else return false;
}

if(p1.squareOfDistance(p2)==p1.squareOfDistance(p3) && p4.squareOfDistance(p2)==p4.squareOfDistance(p3) && p1.squareOfDistance(p2) == p4.squareOfDistance(p3)){
if(isRightAngle(p1,p2,p3)) return true;
else return false;
}
return false;
}
}
```

```#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
const double PI = acos(-1.0);
const double eps = 1e-6;
struct point
{
int x;
int y;
}t[4], temp[4];
struct node
{
point cur;//原点
point xuan;//旋转的点
void scan() { sc("%d%d%d%d", &cur.x, &cur.y, &xuan.x, &xuan.y); }
}in[4];
bool check()
{
for (int i = 0; i < 4; i++)
temp[i] = t[i];
sort(temp, temp + 4, [](point q, point w) {
if (q.x == w.x)
return q.y < w.y;
else
return q.x < w.x;
});
if (temp[0].x == temp[3].x && temp[0].y == temp[3].y)
return false;
if (temp[0].y == temp[2].y && temp[1].y == temp[3].y && temp[0].x == temp[1].x && temp[2].x == temp[3].x && temp[3].y - temp[2].y == temp[3].x - temp[1].x && temp[3].x - temp[1].x == temp[1].y - temp[0].y && temp[1].y - temp[0].y == temp[2].x - temp[0].x)
return true;
return false;
}
point rotate(point a, point o, int angle)//逆时针 angle = angle * 90
{
point t = point{ a.x - o.x,a.y - o.y };
//int c = cos(angle), s = sin(angle);
int c, s;
if (angle == 0)
c = 1, s = 0;
else if (angle == 1)
c = 0, s = 1;
else if (angle == 2)
c = -1, s = 0;
else
c = 0, s = -1;
return point{ o.x + t.x * c - t.y * s,o.y + t.x * s + t.y * c };
}
int main()
{
int T;
sc("%d", &T);
while (T--)
{
for (int i = 0; i < 4; i++)
in[i].scan();
int ans = 100000;
for (int i = 0; i < 4; i++)
{
t[0] = rotate(in[0].cur, in[0].xuan, i);
for (int j = 0; j < 4; j++)
{
t[1] = rotate(in[1].cur, in[1].xuan, j);
for (int k = 0; k < 4; k++)
{
t[2] = rotate(in[2].cur, in[2].xuan, k);
for (int l = 0; l < 4; l++)
{
t[3] = rotate(in[3].cur, in[3].xuan, l);
if (check())
ans = min(ans, i + j + k + l);
}
}
}
}
if (ans == 100000)
ans = -1;
pr("%d\n", ans);
}
}```

```"""

"""
import sys

def rot90(a, b, x, y):
return [y - b + x, a - x + y]

def dis(point1, point2):
return (point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2

def is_square(clutter, i, j, k, t):
point1, point2, point3, point4 = clutter[0][i], clutter[1][j], clutter[2][k], clutter[3][t]
q = [dis(point1, point2), dis(point1, point3), dis(point1, point4), dis(point2, point3), dis(point2, point4),
dis(point3, point4)]
q.sort()
if q[0] > 0 and q[0] == q[1] == q[2] == q[3] == q[4] / 2 == q[5] / 2:
return True
return False

if __name__ == "__main__":
# sys.stdin = open('input.txt', 'r')
n = int(input().strip())
for _ in range(n):
clutter = []
for _ in range(4):
a, b, x, y = list(map(int, input().strip().split()))
tmp = [[a, b]]
for _ in range(3):
tmp.append(rot90(tmp[-1][0], tmp[-1][1], x, y))
clutter.append(tmp)
ans = 100
for i in range(4):
for j in range(4):
for k in range(4):
for t in range(4):
if is_square(clutter, i, j, k, t):
ans = min(ans, i + j + k + t)
if ans > 3 * 4:
ans = -1
print(ans)

```

```#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i != n; ++i) {
vector<vector<pair<int, int>>>edge(4, vector<pair<int, int>>(4, { 0,0 }));
for (int j = 0; j != 4; ++j) {
int a, b, x, y;
cin >> a >> b >> x >> y;
edge[j][0] = { a,b };
for (int k = 1; k != 4; ++k)
edge[j][k] = { x + y - edge[j][k - 1].second,y - x + edge[j][k - 1].first };
}
int mincost = 0x7FFFFFFF;
for (int a = 0; a != 4; ++a)
for (int b = 0; b != 4; ++b)
for (int c = 0; c != 4; ++c)
for (int d = 0; d != 4; ++d) {
vector<pair<int, int>>temp{ edge[0][a],edge[1][b],edge[2][c],edge[3][d] };
sort(temp.begin(), temp.end());
if (temp[1].second - temp[0].second != 0&&
temp[1].second - temp[0].second == temp[2].first - temp[0].first&&
temp[3].second - temp[2].second == temp[2].first-temp[0].first&&
temp[3].second - temp[1].second == temp[1].first-temp[0].first)
mincost = min(mincost, a + b + c + d);
}
cout << (mincost == 0x7FFFFFFF ? -1 : mincost) << endl;
}
return 0;
}
```

```import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException {
int[][][] things = new int[N][4][4];
for(int i=0;i<N;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
things[i][j][k] = Integer.valueOf(s[k]);
}
}
}
for(int i=0;i<N;i++){
System.out.println(calcu(things[i]));
}
}
public static int calcu(int[][] thing){
int ans = Integer.MAX_VALUE;
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++){
int[][] test = new int[4][4];
test[0] = rotate(thing[0],i);
test[1] = rotate(thing[1],j);
test[2] = rotate(thing[2],k);
test[3] = rotate(thing[3],l);
if(isSquare(test)){
ans = Math.min(ans,i+j+k+l);
}
}
}
}
}
return ans == Integer.MAX_VALUE? -1:ans;
}
public static int[] rotate(int[] p,int k){//旋转k次
int[] ans = Arrays.copyOf(p,4);
for(int i=0;i<k;i++){
int x0 = ans[2],y0 = ans[3],x1 = ans[0],y1 = ans[1];
int tmpX = x0 - (y1 - y0);
int tmpY = y0 + (x1 - x0);
ans[0] = tmpX;
ans[1] = tmpY;
}
return ans;
}
public static boolean isSquare(int[][] thing){//各个点不一定是顺序相连的,这样getDistance有可能是求得的对角线的值
//快速判断正方形的方法,正方形,加对角线6条,求出所有点之间的距离6个,从小到大排序,较小4个相等,较大2个相等
long[] arr = new long[6];
arr[0] = getDistance(thing[0],thing[1]);
arr[1] = getDistance(thing[0],thing[2]);
arr[2] = getDistance(thing[0],thing[3]);
arr[3] = getDistance(thing[1],thing[2]);
arr[4] = getDistance(thing[1],thing[3]);
arr[5] = getDistance(thing[2],thing[3]);
Arrays.sort(arr);
return arr[0] == arr[1]
&& arr[0] != 0  //注意,边长不能为0,否则可能出现重合到一点,移动的步数比较小.
&& arr[1] == arr[2]
&& arr[2] == arr[3]
&& arr[4] == arr[5];
}
public static long getDistance(int[] p1,int[] p2){
long xdis = Math.abs(p1[0]-p2[0]);
long ydis = Math.abs(p1[1]-p2[1]);
return xdis*xdis+ydis*ydis;
}
}```

```#include <iostream>
using namespace std;

struct Vec2i
{
Vec2i() : x(0), y(0) {}
Vec2i(int x, int y) : x(x), y(y) {}

int x;
int y;
};

Vec2i operator-(const Vec2i& p1, const Vec2i& p2) { return Vec2i(p1.x-p2.x, p1.y-p2.y); }

int distSq(const Vec2i& p) { return p.x*p.x + p.y*p.y; }

bool isRightAngle(const Vec2i& d1, const Vec2i& d2)
{
if (d1.x == 0 && d1.y == 0) return false;
if (d2.x == 0 && d2.y == 0) return false;

int dot = d1.x*d2.x + d1.y*d2.y;
return dot == 0;
}

bool isSquare(const Vec2i& p1, const Vec2i& p2, const Vec2i& p3, const Vec2i& p4)
{
Vec2i d12 = p2 - p1;
Vec2i d13 = p3 - p1;
Vec2i d14 = p4 - p1;
Vec2i d23 = p3 - p2;
Vec2i d24 = p4 - p2;
Vec2i d34 = p4 - p3;

int length12 = distSq(d12);
int length13 = distSq(d13);
int length14 = distSq(d14);
int length23 = distSq(d23);
int length24 = distSq(d24);
int length34 = distSq(d34);

if (isRightAngle(d13, d14) && length13 == length14 && isRightAngle(d23, d24) && length23 == length24)
return true; // 12 diagonal
if (isRightAngle(d12, d14) && length12 == length14 && isRightAngle(d23, d34) && length23 == length34)
return true; // 13 diagonal
if (isRightAngle(d12, d13) && length12 == length13 && isRightAngle(d24, d34) && length24 == length34)
return true; // 14 diagonal
return false;
}

Vec2i rotate90(const Vec2i& p, const Vec2i& center)
{
int dx = p.x - center.x;
int dy = p.y - center.y;
return Vec2i(-dy + center.x, dx + center.y);
}

void computeRotated(Vec2i rotated[4], const Vec2i& p, const Vec2i& center)
{
rotated[0] = p;
for (int i = 1; i < 4; ++i) rotated[i] = rotate90(rotated[i - 1], center);
}

int minRotationSteps(Vec2i p1, Vec2i p2, Vec2i p3, Vec2i p4, Vec2i c1, Vec2i c2, Vec2i c3, Vec2i c4)
{
Vec2i p1Rotated[4];
Vec2i p2Rotated[4];
Vec2i p3Rotated[4];
Vec2i p4Rotated[4];

// compute all rotated points
computeRotated(p1Rotated, p1, c1);
computeRotated(p2Rotated, p2, c2);
computeRotated(p3Rotated, p3, c3);
computeRotated(p4Rotated, p4, c4);

// find min steps
int min = 100;
for (int i1 = 0; i1 < 4; ++i1) {
for (int i2 = 0; i2 < 4; ++i2) {
for (int i3 = 0; i3 < 4; ++i3) {
for (int i4 = 0; i4 < 4; ++i4) {

int steps = i1 + i2 + i3 + i4;
if (steps < min && isSquare(p1Rotated[i1], p2Rotated[i2], p3Rotated[i3], p4Rotated[i4]))
min = steps;
}
}
}
}

if (min == 100) return -1; // no solutions
else return min;
}

int main()
{
int N;
cin >> N;

Vec2i p1, p2, p3, p4, c1, c2, c3, c4;

while (N--) {
cin >> p1.x >> p1.y >> c1.x >> c1.y;
cin >> p2.x >> p2.y >> c2.x >> c2.y;
cin >> p3.x >> p3.y >> c3.x >> c3.y;
cin >> p4.x >> p4.y >> c4.x >> c4.y;

cout << minRotationSteps(p1, p2, p3, p4, c1, c2, c3, c4) << endl;
}

return 0;
}```

```import java.util.*;
public class Main{

private static Scanner sc;

public static void main(String[] args){
sc = new Scanner(System.in);
int n = sc.nextInt();
int[][][] abxy = new int[n][4][4];
for(int i = 0;i<n;i++){
for(int j = 0;j<4;j++){
for(int k = 0;k<4;k++){
abxy[i][j][k] = sc.nextInt();
}
}
}
int min;
for(int i = 0;i<n;i++){
min = Integer.MAX_VALUE;
for(int cnt1 = 0;cnt1<4;cnt1++){
for(int cnt2 = 0;cnt2<4;cnt2++){
for(int cnt3 = 0;cnt3<4;cnt3++){
for(int cnt4 = 0;cnt4<4;cnt4++){
if(isSquare(rotate(abxy[i][0],cnt1),
rotate(abxy[i][1],cnt2),
rotate(abxy[i][2],cnt3),
rotate(abxy[i][3],cnt4)))
min = Math.min(min,cnt1+cnt2+cnt3+cnt4);
}
}
}
}
System.out.println(min == Integer.MAX_VALUE?-1:min);
}
}

private static int[] rotate(int[] nums,int times){
int[] res = new int[4];
if(times == 0)
return nums;
else{
res[2] = nums[2];
res[3] = nums[3];
res[0] = nums[2]-nums[1]+nums[3];
res[1] = nums[0]-nums[2]+nums[3];
return rotate(res,times-1);
}
}
private static boolean isSquare(int[] p1,int[] p2,int[] p3,int[] p4){
int px1 = p1[0],py1 = p1[1];
int px2 = p2[0],py2 = p2[1];
int px3 = p3[0],py3 = p3[1];
int px4 = p4[0],py4 = p4[1];
if((px1 ^ px2 ^ px3 ^ px4) != 0)
return false;
if((py1 ^ py2 ^ py3 ^ py4) != 0)
return false;
if(px1 == px2 && px1 == px3)
return false;
if(py1 == py2 && py1 == py3)
return false;
int edge1 = Math.abs((px1-px2) == 0?px1-px3:px1-px2);
int edge2 = Math.abs((py1-py2) == 0?py1-py3:py1-py2);
return edge1 == edge2;
}
}```

（1）平面中，一个点(x,y)绕任意点(dx,dy)逆时针旋转a度后的坐标

xx= (x - dx)*cos(a) - (y - dy)*sin(a) + dx ;

yy= (x - dx)*sin(a) + (y - dy)*cos(a) +dy ;

```
#include<bits/stdc++.h> //万能的头文件
using namespace std;
//Point类
typedef struct Point
{
//坐标
int x;
int y;
//绕着旋转的点
int a;
int b;
Point(int a1,int a2,int a3,int a4):x(a1),y(a2),a(a3),b(a4){}
Point(){}
}P;

//一个点逆时针旋转n次的坐标
P rotate(P point,int times)
{
int x = point.x;
int y = point.y;
int a = point.a;
int b = point.b;
for(int i = 1;i<=times;i++)
{
int xx = a+b-y;
int yy = x+b-a;
x = xx;
y = yy;
}
return Point(x,y,a,b);
}
//判断直角，向量p1p2乘以向量p1p3,结果为0，则两段垂直
bool is_Angle(P p1,P p2,P p3)
{
return  ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))==0;
}
//两点距离，这里测试用例都是整数
int distance(P p1,P p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
//判断是正方形
bool is_Square(P p1,P p2,P p3,P p4)
{
//保存到数组中
vector<Point> nums(4);
nums[0] = p1;
nums[1] = p2;
nums[2] = p3;
nums[3] = p4;
//要排序的，排序后就知道4个坐标的位置顺序
sort(nums.begin(),nums.end(),[](P a,P b){
return a.x==b.x?a.y<b.y:a.x<b.x;
});
int d1 = distance(nums[0],nums[1]);
int d2 = distance(nums[0],nums[2]);
int d3 = distance(nums[1],nums[3]);
int d4 = distance(nums[2],nums[3]);
//这里要判断4段距离相等且不为0，一个角为90°，就是正方形
if(d1!=0&&d1==d2&&d2==d3&&d3==d4&&is_Angle(nums[0],nums[1],nums[2]))
return true;
else
return false;
}
int main(void)
{
int n;
cin>>n;
vector<Point> nums(4);
for(int i = 0;i<n;i++)
{
for(int j =0;j<4;j++)
cin>>nums[j].x>>nums[j].y>>nums[j].a>>nums[j].b;
int count  = INT_MAX;
//四重循环，每个点最多转3次，起始循环不大
for(int m=0;m <4;m++)
for(int n=0;n <4;n++)
for(int k=0;k <4;k++)
for(int l=0;l <4;l++)
{
//旋转后是正方形，则记录
if(is_Square(rotate(nums[0],m),rotate(nums[1],n),rotate(nums[2],k),rotate(nums[3],l)))
{
count = min(count,m+n+k+l);
}
}
//输出最小值
count = count==INT_MAX?-1:count;
cout<<count<<endl;
}
return 0;
}

```

38条回答 12004浏览

# 通过挑战的用户

• 2020-09-26 21:53:06
• 2020-09-10 11:41:07
• 2020-09-07 17:16:00
• 2020-08-31 17:12:35
• 2020-08-25 16:40:17

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题