网易校招题之整理房间

参考自：https://blog.csdn.net/qq_36381573/article/details/100089207

题目描述

第一行一个数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次。

#include<bits/stdc++.h>
using namespace std;
struct Point {
	int x;
	int y;
	int a;
	int b;
	Point(int x, int y, int a, int b) 
    {
		this->x = x;
		this->y = y;
		this->a = a;
		this->b = b;
	}
	Point() {}
};
Point rotate(Point p, int times) 
{//计算旋转之后的坐标
	int x = p.x;
	int y = p.y;
	int a = p.a;
	int b = p.b;
	int xx, yy;
	for (int i = 0; i < times; i++) 
    {
		xx = a - y + b;
		yy = x - a + b;
		x = xx;
		y = yy;
	}
	return Point(x, y, a, b);
}
bool cmp(Point p1, Point p2) 
{//自定义排序顺序
	if (p1.x != p2.x) 
    {
		return p1.x < p2.x;
	}
	return p1.y < p2.y;
}
bool isRightAngle(Point p1, Point p2, Point p3) 
{//判断是否有直角
	int x = (p1.x - p2.x)*(p1.x - p3.x) + (p1.y - p2.y)*(p1.y - p3.y);
	if (x == 0) 
    {
		return true;
	}
	return false;
}
int distance(Point p1, Point p2) 
{//计算两点之间的距离，正方形四边相等
	return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
bool isSquare(Point p1,Point p2,Point p3,Point p4) 
{//判断是否是正方形
	vector<Point> points(4);
	points[0] = p1;
	points[1] = p2;
	points[2] = p3;
	points[3] = p4;
	sort(points.begin(), points.end(), cmp);
	int s1 = distance(points[0],points[1]);
	int s2 = distance(points[0], points[2]);
	int s3 = distance(points[1], points[3]);
	int s4 = distance(points[2], points[3]);
	if (s1 == s2 && s2 == s3 && s3 == s4 && s1 != 0 && isRightAngle(points[0], points[1], points[2])) 
    {
		return true;
	}
	else 
    {
		return false;
	}
}

int main() 
{
	int N; cin >> N;
	vector<Point> nums(4);
	
	for (int index = 0; index < N; index++) {
		for (int i = 0; i < 4; i++) {
			cin >> nums[i].x >> nums[i].y >> nums[i].a >> nums[i].b;
		}
		int count = INT_MAX;
		for (int m = 0; m < 4; m++) {
			for (int n = 0; n < 4; n++) {
				for (int p = 0; p < 4; p++) {
					for (int q = 0; q < 4; q++) {
						if (isSquare(rotate(nums[0], m), rotate(nums[1], n), rotate(nums[2], p), rotate(nums[3], q)))
                                                {
							count = min(count, m + n + p + q);
						}
					}
				}
			}
		}
		count = count == INT_MAX ? -1 : count;
		cout << count << endl;
	}
	return 0;
}