首页 > 试题广场 >

整理房间

[编程题]整理房间
  • 热度指数：5627 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
又到了周末，小易的房间乱得一团糟。
他希望将地上的杂物稍微整理下，使每团杂物看起来都紧凑一些，没有那么乱。
地上一共有n团杂物，每团杂物都包含4个物品。第i物品的坐标用(ai,bi)表示，小易每次都可以将它绕着(xi,yi)逆时针旋转，这将消耗他的一次移动次数。如果一团杂物的4个点构成了一个面积不为0的正方形，我们说它是紧凑的。
因为小易很懒，所以他希望你帮助他计算一下每团杂物最少需要多少步移动能使它变得紧凑。

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


输出描述:
n行，每行1个数，表示最少移动次数。
示例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次。
算法知识视频讲解
添加回答
Python
果然多头像 果然多 
import sys def point(sourse,t): p=[] if t == 0:
        p = [sourse[0], sourse[1]] elif t == 1:
        p = [sourse[2] + sourse[3] - sourse[1],  -sourse[2] + sourse[3] + sourse[0]] elif t == 2:
        p = [2 * sourse[2] - sourse[0], 2 * sourse[3] - sourse[1]] else:
        p = [sourse[2] - sourse[3] + sourse[1],  sourse[2] + sourse[3] - sourse[0]] return p def isSqu(p1,p2,p3,p4):
    d1=  (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2  d2 = (p1[0] - p3[0]) ** 2 + (p1[1] - p3[1]) ** 2  d3 = (p1[0] - p4[0]) ** 2 + (p1[1] - p4[1]) ** 2  d4 = (p2[0] - p3[0]) ** 2 + (p2[1] - p3[1]) ** 2  d5 = (p2[0] - p4[0]) ** 2 + (p2[1] - p4[1]) ** 2  d6 = (p3[0] - p4[0]) ** 2 + (p3[1] - p4[1]) ** 2  dic={}
    arr=[d1,d2,d3,d4,d5,d6] for item in arr: if item in dic.keys():
            dic[item]=dic[item]+1  else:
            dic[item]=1  if len(dic)==2 and (dic[d1]==2 or dic[d1]==4) and not dic.__contains__(0): return 1  else: return 0  n=int(input())
sourse=[] for i in range(4*n):
    str=sys.stdin.readline()
    sourse.append([int(str.split()[0]),int(str.split()[1]),int(str.split()[2]),int(str.split()[3])]) for i in range(n):
    temp=16  flag=0  for t1 in range(4):
        p1=point(sourse[4*i],t1) for t2 in range(4):
            p2=point((sourse[4*i+1]),t2) for t3 in range(4):
                p3=point(sourse[4*i+2],t3) for t4 in range(4):
                    p4=point(sourse[4*i+3],t4) if isSqu(p1,p2,p3,p4):
                        flag=1  temp = min(t1 + t2 + t3 + t4, temp) #print(p1,p2,p3,p4,t1+t2+t3+t4)   if flag==0:
        temp=-1    print(temp)
发表于 2019-11-04 23:47:54 回复(0)
Python
自闭中的薯条头像 自闭中的薯条
mport pdb
def Trang(P1,P2,P3,P4):
    Flag = 0
    if (P1[0]-P2[0])*(P3[0]-P4[0])+(P1[1]-P2[1])*(P3[1]-P4[1])==0:
        if (P1[0]+P2[0])/2 == (P3[0]+P4[0])/2:
            if (P1[1]+P2[1])/2 == (P3[1]+P4[1])/2:
                if (P1[0]-P2[0])**2+(P1[1]-P2[1])**2 == (P3[0]-P4[0])**2+(P3[1]-P4[1])**2:
                    if not((P1[0]==P2[0]==P3[0]==P4[0])and(P1[1]==P2[1]==P3[1]==P4[1])):
                        Flag = 1
    if (P1[0]-P3[0])*(P2[0]-P4[0])+(P1[1]-P3[1])*(P2[1]-P4[1])==0:
        if (P1[0]+P3[0])/2 == (P2[0]+P4[0])/2:
            if (P1[1]+P3[1])/2 == (P2[1]+P4[1])/2:
                if (P1[0]-P3[0])**2+ (P1[1]-P3[1])**2 == (P2[0]-P4[0])**2+(P2[1]-P4[1])**2:
                    if not((P1[0]==P2[0]==P3[0]==P4[0])and(P1[1]==P2[1]==P3[1]==P4[1])):
                        Flag = 1    
    if (P1[0]-P4[0])*(P3[0]-P2[0])+(P1[1]-P4[1])*(P3[1]-P2[1])==0:
        if (P1[0]+P4[0])/2 == (P3[0]+P2[0])/2:
            if (P1[1]+P4[1])/2 == (P3[1]+P2[1])/2:
                if (P1[0]-P4[0])**2+(P1[1]-P4[1])**2 == (P2[0]-P3[0])**2+(P2[1]-P3[1])**2:
                    if not((P1[0]==P2[0]==P3[0]==P4[0])and(P1[1]==P2[1]==P3[1]==P4[1])):
                        Flag = 1
    return Flag

def main():
    N = int(raw_input())
    L = []
    for i in range(N):
        L.append(raw_input())
        L.append(raw_input())
        L.append(raw_input())
        L.append(raw_input())
    L0 = [];
    Dict0 = {}
    Dict1 = {}
    Dict2 = {}
    Dict3 = {}
    cishu = []
    for i in range(N):
        L0 = L[4*i:4*i+4]
        a,b,x,y = L0[0].split()
        Dict0[0] = [int(a)-int(x)+int(x),int(b)-int(y)+int(y)]
        Dict0[1] = [int(y)-int(b)+int(x),int(a)-int(x)+int(y)]
        Dict0[2] = [int(x)-int(a)+int(x),int(y)-int(b)+int(y)]
        Dict0[3] = [int(b)-int(y)+int(x),int(x)-int(a)+int(y)]
        a,b,x,y = L0[1].split()
        Dict1[0] = [int(a)-int(x)+int(x),int(b)-int(y)+int(y)]
        Dict1[1] = [int(y)-int(b)+int(x),int(a)-int(x)+int(y)]
        Dict1[2] = [int(x)-int(a)+int(x),int(y)-int(b)+int(y)]
        Dict1[3] = [int(b)-int(y)+int(x),int(x)-int(a)+int(y)]
        a,b,x,y = L0[2].split()
        Dict2[0] = [int(a)-int(x)+int(x),int(b)-int(y)+int(y)]
        Dict2[1] = [int(y)-int(b)+int(x),int(a)-int(x)+int(y)]
        Dict2[2] = [int(x)-int(a)+int(x),int(y)-int(b)+int(y)]
        Dict2[3] = [int(b)-int(y)+int(x),int(x)-int(a)+int(y)]
        a,b,x,y = L0[3].split()
        Dict3[0] = [int(a)-int(x)+int(x),int(b)-int(y)+int(y)]
        Dict3[1] = [int(y)-int(b)+int(x),int(a)-int(x)+int(y)]
        Dict3[2] = [int(x)-int(a)+int(x),int(y)-int(b)+int(y)]
        Dict3[3] = [int(b)-int(y)+int(x),int(x)-int(a)+int(y)]
        cishu0 = [];flag=0;
        for c in range(4):
            P0 = Dict0[c]
            for d in range(4):
                P1 = Dict1[d]
                for e in range(4):
                    P2 = Dict2[e]
                    for f in range(4):
                        P3 = Dict3[f]
                        if Trang(P0,P1,P2,P3):
                            flag=1
                            cishu0.append(c+d+e+f)
        if flag == 1:
            cishu.append(min(cishu0))
        else:
            cishu.append(-1)
    for i in range(len(cishu)):
        print cishu[i]                   
main() 
发表于 2019-08-10 21:43:38 回复(0)
Python
ElonB头像 ElonB 
"""
列出逆时针旋转所有可能的坐标点，
枚举4*4*4*4种可能组合，找到最小可组成方形的旋转次数
"""
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)

发表于 2019-07-03 17:06:50 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 PHP工程师 模拟 穷举 网易 2019 数学 Java工程师
来自：网易2019秋季校园招...
上传者：小小
难度：
3条回答 15986浏览

热门推荐

通过挑战的用户

查看代码

相关试题

整理房间

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号