查找四个点,使它们形成一个正方形,其边与Python中的x和y轴平行
假设我们有n对点;我们必须找到四个点,以便它们可以生成一个边与x和y轴平行的正方形,否则将返回“不可能”。如果我们找到多个正方形,则选择面积最大的正方形。
因此,如果输入像n=6,则点=[(2,2),(5,5),(4,5),(5,4),(2,5),(5,2)],则输出为3,点为(2,2)(5,2)(2,5)(5,5)
为了解决这个问题,我们将遵循以下步骤-
my_map:=新映射
对于0到n范围内的i,执行
my_map[(points[i,0],points[i,1])]=my_map。[(points[i,0],points[i,1]],0)+1
边:=-1
x:=-1
y:=-1
对于0到n范围内的i,执行
my_map[points[j,0],points[j,1]]:=my_map[points[j,0],points[j,1]]-1
如果(i与j不相同,并且(points[i,0]-points[j,0])与(points[i,1]-points[j,1])相同,则
my_map[points[j,0],points[j,1]]:=my_map[points[j,0],points[j,1]]+1
if(side<|points[i,0]-points[j,0]|or(side与|points[i,0]-points[j,0]|和((points[i,0]*points[i,0]+points[i,1]*points[i,1])<(x*x+y*y))))-
x:=points[i,0]
y:=points[i,1]
边:=|points[i,0]-points[j,0]|
如果my_map[(points[i,0],points[j,1])]>0和my_map[(points[j,0],points[i,1])]>0,则
my_map[points[i,0],points[i,1]]:=my_map[points[i,0],points[i,1]]-1
对于0到n范围内的j,执行
my_map[points[i,0],points[i,1]]:=my_map[points[i,0],points[i,1]]+1
如果side与-1不同,则
显示面
显示点(x,y),(x+边,y),(x,y+边),(x+边,y+边)
除此以外,
显示“没有这样的正方形”
示例
让我们看下面的实现以更好地理解-
def get_square_points(points,n): my_map = dict() for i in range(n): my_map[(points[i][0], points[i][1])] = my_map.get((points[i][0], points[i][1]), 0) + 1 side = -1 x = -1 y = -1 for i in range(n): my_map[(points[i][0], points[i][1])]-=1 for j in range(n): my_map[(points[j][0], points[j][1])]-=1 if (i != j and (points[i][0]-points[j][0]) == (points[i][1]-points[j][1])): if (my_map[(points[i][0], points[j][1])] > 0 and my_map[(points[j][0], points[i][1])] > 0): if (side < abs(points[i][0] - points[j][0]) or (side == abs(points[i][0] - points[j][0]) and ((points[i][0] * points[i][0] + points[i][1] * points[i][1]) < (x * x + y * y)))): x = points[i][0] y = points[i][1] side = abs(points[i][0] - points[j][0]) my_map[(points[j][0], points[j][1])] += 1 my_map[(points[i][0], points[i][1])] += 1 if (side != -1): print("Side:", side) print("Points:", (x,y), (x+side, y), (x,y + side), (x+side, y+side)) else: print("No such square") n = 6 points=[(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)] get_square_points(points, n)
输入值
6, [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]
输出结果
Side: 3 Points: (2, 2) (5, 2) (2, 5) (5, 5)