首页 > 试题广场 >

整理房间

[编程题]整理房间
  • 热度指数：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次。
算法知识视频讲解
开通博客
头像 0x0offer的菜鸡
发表于 2019-08-27 09:39:43
  思路：这个题目是比较考察人的编程能力的，最简单的方法就是暴力枚举，依次把每个点旋转4次（旋转0次、1次、2次、3次），判断旋转之后的点是否构成正方形。  这个题的难点有两个部分，一是旋转后的坐标的确定，二是判断给定任意四个点，它们是否能够成正方形。下面我将从这两个部分分别说明： 1.旋转后的坐标 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 诗云panther
发表于 2021-08-20 12:39:07
include <stdio.h> include <math.h> typedef struct node{ int x,y;}node;bool judge(int a1 ,int b1 ,int a2 ,int b2,int a3,int b3,int a4,in 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 laglangyue
发表于 2020-05-18 23:43:27
总体思路仍然是枚举所有情况，面向对象，可读性高，为了防止代码过长，没有进行属性封装。用一个对象数组存储四个角点，通过实现comparator接口实现排序，通过排序保证了数组 0和3的对象是对角角点，于是对角线就是0，3 和 1，2对角线中点重合，对角线长度相等且大于0，对角线互相垂直>> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客题解官
发表于 2020-06-04 14:34:36
题目难度：三星考察点：计算几何 方法：计算几何、枚举 分析：对于这道题来说我们有如下需要考虑的地方：(1). 一个点A(x1,y1)围绕一个点B(x2,y2)逆时针旋转90°一次，对应坐标A的变化？旋转多次呢？我们都知道如果B是原点的话，那么逆时针旋转90°一次之后坐标A(x1,y1)将变为C(y 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

整理房间

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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