网易2019校招算法题

这里只记录最后一道算法题：
题目如下：地上有n团杂物，每团杂物包含4个物品，第i个物品坐标(xi,yi),每次可以将它绕着(a,b)逆时针旋转90度，这将消耗一次移动次数，如果一团杂物4个点组成了一个面积不为0的正方形，则紧凑，求步数

• 输入：第一行位杂物团数n(1<= n <=100),接下来4n行，每4行表示一团杂物，每行xi,yi,ai,bi(-10^4 <= xi,yi,ai,bi <= 10^4)，表示物品坐标和旋转中点

• 输出：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
2 2 0 1
-1 0 0 -2
3 0 0 -2
-1 1 -2 0

输出

1
-1
3

主体代码如下：

#! /bin/env python
# -*- coding: utf-8 -*-


class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y


def dis(a, b):
    """
    对角线相等
    """
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)


def mid(a, b, c, d):
    """
    对角线中点一致
    """
    if a.x + b.x == c.x + d.x and a.y + b.y == c.y + d.y:
        return True
    else:
        return False


def isSquare(a, b, c, d):
    """
    再加邻边相等
    """
    if dis(a, b) == dis(c, d) and mid(a, b, c, d) and dis(a, c) == dis(a, d):
        return True
    if dis(a, c) == dis(b, d) and mid(a, c, b, d) and dis(a, b) == dis(a, d):
        return True
    if dis(a, d) == dis(b, c) and mid(a, d, b, c) and dis(a, b) == dis(a, c):
        return True
    return False


def rotate(a, target_a):
    """
    逆时针旋转90
    """
    x = (a.x - target_a.x)*0 - (a.y - target_a.y)*1 + target_a.x
    y = (a.x - target_a.x)*1 + (a.y - target_a.y)*0 + target_a.y
    return Point(x, y)


def main(array):
    target_a = Point(array[0][2], array[0][3])
    target_b = Point(array[1][2], array[1][3])
    target_c = Point(array[2][2], array[2][3])
    target_d = Point(array[3][2], array[3][3])
    a = Point(array[0][0], array[0][1])
    b = Point(array[1][0], array[1][1])
    c = Point(array[2][0], array[2][1])
    d = Point(array[3][0], array[3][1])
    ori_a = a
    ori_b = b
    ori_c = c
    ori_d = d
    flag_array = []
    for i in range(4):
        for j in range(4):
            for m in range(4):
                for n in range(4):
                    flag_array.append([i, j, m, n])
    for item in flag_array:
        a = ori_a
        b = ori_b
        c = ori_c
        d = ori_d
        for i in range(item[0]):
            a = rotate(a, target_a)
        for i in range(item[1]):
            b = rotate(b, target_b)
        for i in range(item[2]):
            c = rotate(c, target_c)
        for i in range(item[3]):
            d = rotate(d, target_d)
        if isSquare(a, b, c, d):
            print(item[0], item[1], item[2], item[3])
            return item[0]+item[1]+item[2]+item[3]
    return -1

if __name__ == "__main__":
    # array = [[2,2,1,1],[0,2,1,1],[0,2,1,1],[2,0,1,1]]
    # array = [[1,1,0,0],[-1,1,0,0],[-1,1,0,0],[1,-1,0,0]]
    array = [[2,2,0,1],[-1,0,0,-2],[3,0,0,-2],[-1,1,-2,0]]
    print(main(array))

方法比较简单，其中主要有两个地方值得注意，一个是正方形的判断，还有一个是旋转之后坐标的公式，可以参考如下博客：csdn