如何在一组给定的点上找到一个正方形？

-3

在一个坐标平面上，给出了一组点，比如说10个点，为了简单起见，可以认为它们是整数。要找出一个可能的正方形是否在这10个点内？.... if不是，要添加到这些点的点数至少有一个平方？如何在一组给定的点上找到一个正方形？

嗯，这是最多需要添加的两点。 – 2014-10-12 10:44:22

如果仅给出1分，则必须添加3分 – 2014-10-12 10:45:25

您刚才说有10个给定分数。 – 2014-10-12 10:46:03

只要使用蛮力。对于集合中的每个点，对于集合中的每个可能的其他点，检查是否有两个点足够接近可能的其他方形拐角。如果坐标是整数，那么这非常简单（尽管具有二次方复杂性，假设点查找的时间不变），当浮点稍微简单一点而且复杂度稍高时，可能是这样。

2014-10-12 10:53:57

蛮力方法是计算“nC2”距离并进行比较，但这无法帮助我得出可能需要多少点。 – 2014-10-12 10:56:42

@peterburke：会的。如果你找到一个正方形，答案是0.如果你找到一个角落，那么答案是1.如果你找不到角落，那么答案是2. – 2014-10-12 10:57:37

会尝试并给它一个镜头，谢谢 – 2014-10-12 10:58:19

回答