資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 Python 中查詢四個點，使它們形成一個邊平行於 x 軸和 y 軸的正方形
假設我們有 n 對點；我們需要找到四個點，以便它們可以生成一個邊平行於 x 軸和 y 軸的正方形，否則返回“不可能”。如果我們能找到多個正方形，則選擇面積最大的那個。
因此，如果輸入類似於 n = 6，points = [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]，則輸出將是 3，點為 (2, 2) (5, 2) (2, 5) (5, 5)
為了解決這個問題，我們將遵循以下步驟 -
my_map := 一個新的對映
對於 i 的範圍從 0 到 n，執行
my_map[(points[i,0], points[i,1])] = my_map.[(points[i,0], points[i,1]], 0) + 1
side := -1
x := -1
y := -1
對於 i 的範圍從 0 到 n，執行
my_map[points[i, 0], points[i, 1]] := my_map[points[i, 0], points[i, 1]] - 1
對於 j 的範圍從 0 到 n，執行
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[i,0], points[j, 1])] > 0 且 my_map[(points[j,0], points[i,1])] > 0，則
如果 (side < |points[i,0] - points[j,0]| 或 (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]
side := |points[i,0] - points[j,0]|
my_map[points[j, 0], points[j, 1]] := my_map[points[j, 0], points[j, 1]] + 1
my_map[points[i, 0], points[i, 1]] := my_map[points[i, 0], points[i, 1]] + 1
如果 side 不等於 -1，則
顯示 side
顯示點 (x,y), (x+side, y), (x,y + side), (x+side, y+side)
否則，
顯示“沒有這樣的正方形”
示例
讓我們看看以下實現以獲得更好的理解 -
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)
402 次檢視
