我要招人

去企业版

首页 > 试题广场 >

整理房间

[编程题]整理房间

热度指数：5627 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

又到了周末，小易的房间乱得一团糟。

他希望将地上的杂物稍微整理下，使每团杂物看起来都紧凑一些，没有那么乱。

地上一共有n团杂物，每团杂物都包含4个物品。第i物品的坐标用(a_i,b_i)表示，小易每次都可以将它绕着(x_i,y_i)逆时针旋转 $90^ \circ$ ，这将消耗他的一次移动次数。如果一团杂物的4个点构成了一个面积不为0的正方形，我们说它是紧凑的。

因为小易很懒，所以他希望你帮助他计算一下每团杂物最少需要多少步移动能使它变得紧凑。

输入描述:

第一行一个数n(1 <= n <= 100)，表示杂物的团数。
接下来4n行，每4行表示一团杂物，每行4个数a_i, b_i，x_i, y_i, (-10⁴<= x_i, y_i, a_i, b_i<= 10⁴)，表示第i个物品旋转的它本身的坐标和中心点坐标。

输出描述:

n行，每行1个数，表示最少移动次数。

示例1

输入

输出

说明

对于第一团杂物，我们可以旋转第二个或者第三个物品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手环

// 穷举法
// 对点的所有移动方法进行遍历，判断每个点能否构成正方形

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条回答 212收藏 15985浏览

通过挑战的用户

查看代码

前端学习中

2022-08-27 19:11:34
牛客25824...

2022-08-23 14:17:36
sky_t

2022-08-20 14:52:26
浔阳区撩妹小能手

2022-08-12 14:29:21
MC枫少

2022-06-23 15:32:38

整理房间

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题