如何求能覆盖所有平面上给出点的三个最小的正方形

PMS

2018/12/15镜像同步8 回复

平面上给出若干点，如果用三个最小的正方形覆盖住所有点，如果求出这个三个最小的正方形？

订阅后，新回复会通过你的通知中心匿名送达。

8 条回复

BYACY机器人#1 · 2018/12/16

随机化算法

lanvent机器人#2 · 2018/12/16

第一问Poj3301 【在 PMS (PMS) 的大作中提到: 】 : 平面上给出若干点，如果用一个小正方形覆盖住所有点，如果求出这个正方形？正方形可以以任意角度摆放，不必平行于x,y轴 : 第二问是换成三个小正方形，如何求出 : --

g1007284540机器人#3 · 2018/12/16

找到最远的两个点做对角线？第一反应是这个

ryg940723机器人#4 · 2018/12/16

可以搜索不规则图形最小化外接矩形MBR（Minimum Bounding Rectangle）然后从这个最小化外接矩形拓展到最小外接正方形

PMS机器人#5 · 2018/12/19

【在 lanvent 的大作中提到: 】 : 第一问Poj3301 太感谢了

SeymourLee机器人#6 · 2018/12/28

楼主你知道三个正方形那个怎么解吗？学弟也在面Quora北美，这个题也不会。求教啊！！！

PMS机器人#7 · 2019/1/11

【在 SeymourLee 的大作中提到: 】 : 楼主你知道三个正方形那个怎么解吗？学弟也在面Quora北美，这个题也不会。求教啊！！！学弟好，这题我最后也没找到答案，然后quora面完两天后就出拒信了。第二轮是serialize and deserialize string + next permutation 第三轮是探测器题第四轮是随机map 我第一轮上机所有小问全做完了，后面三轮题也全都秒了，bq答的也比较流畅，不知道为什么秒出拒信，真是服

SeymourLee机器人#8 · 2019/1/12

学长你好，我周三intern onsite，昨天给了拒信，虽然答得一般吧，但还是挺难受的。这家bar很迷，学长也move on吧！祝学长顺利！！！【在 PMS 的大作中提到: 】 : : 学弟好，这题我最后也没找到答案，然后quora面完两天后就出拒信了。 : 第二轮是serialize and deserialize string + next permutation : ...................