首页 > 试题广场 >

整理房间

[编程题]整理房间
  • 热度指数：5623 时间限制：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次。
算法知识视频讲解
添加回答
JavaScript
萌萌萌哒头像 萌萌萌哒
JavaScript(Node) 😎题目:网易-整理房间（穷举） 
const readline = require('readline');
const lines = [];
const rl = readline.createInterface({
  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;
}
发表于 2020-02-26 11:26:42 回复(0)
JavaScript
AC手环头像 AC手环 
// 穷举法
// 对点的所有移动方法进行遍历，判断每个点能否构成正方形

function rotate(a, b, x, y){
    return [x+y-b, y+a-x]
}

function dis(a1,b1, a2,b2){
    return (a2 - a1) ** 2 + (b2 - b1) ** 2
}
function isSquare(...points){ // [[x,y], [x, y]]
    
    let edges = []
    for(let i = 0; i < 3; i++){
        for(let j = i+1; j < 4; j++){
            edges.push(dis(...points[i], ...points[j]))
        }
    }
    edges.sort((x,y)=>x-y)
    if (edges[0] != 0 && // 面积不为0
        edges.slice(0, 4).every(d=>d===edges[0]) && // 前四个边相同
        edges.slice(4).every(d=>d===edges[4]) &&  // 后两个对角线相同
        edges[4] == 2 * edges[0]){ // 对角线的平方是边长的两倍
        
        return true
    }  
    
    return false
}
function solve(arrMap){
    let counter = 0
    let min = 100
    
    let temp = arrMap.map(d=>{
        let [a,b,x,y] = d
        let allRotate = [[a,b]]
        
        for(let i = 0; i < 3; i++){
            allRotate.push(rotate(...allRotate[allRotate.length - 1], x, y))
        }
        return allRotate
    })

    for(let i = 0; i < 4; i++){
        for(let j = 0; j < 4; j++){
            for(let m = 0; m < 4; m++){
                for(let n = 0; n < 4; n++){
                    if(isSquare(temp[0][i], temp[1][j], temp[2][m], temp[3][n])){
                        min = Math.min(min, i+j+m+n)
                    }
                }
            }
        }
    }
    
    return min === 100 ? -1 : min
}

let n = +readline()
let inputs = []
for(let i = 0; i < n; i++){
    let temp = []
    for(let i = 0; i< 4; i++){
        temp.push(readline().split(' ').map(d=>+d))
    }
    
    inputs.push(temp)
}
    
 for(let i = 0; i < n; i++){
    let result = solve(inputs[i])
    console.log(result)
}

发表于 2019-08-22 12:55:45 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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