मान लीजिए कि हमारे पास 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 की सीमा में, करें
-
my_map[(अंक [i,0], अंक [i,1])] =my_map। [(अंक [i,0], अंक [i,1]], 0) + 1
-
-
पक्ष :=-1
-
x :=-1
-
वाई:=-1
-
मेरे लिए 0 से n की सीमा में, करें
-
my_map [अंक [i, 0], अंक [i, 1]]:=my_map [अंक [i, 0], अंक [i, 1]] - 1
-
j के लिए 0 से n की सीमा में, करें
-
my_map[points[j, 0], points[j, 1]]:=my_map[points[j, 0], points[j, 1]] - 1
-
अगर (मैं जे के समान नहीं है और (अंक [i,0] - अंक [जे, 0]) समान है (अंक [i,1]- अंक [जे, 1])), तो
-
अगर my_map[(points[i,0], points[j, 1])]> 0 and my_map[(points[j,0], points[i,1])]> 0, तब
-
अगर (पक्ष <| अंक [i, 0] - अंक [जे, 0] | या (पक्ष | अंक [i, 0] के समान है - अंक [जे, 0] | और ((अंक [i,0] * अंक [i,0] + अंक [i,1] * अंक [i,1]) <(x * x + y * y))) -
-
एक्स:=अंक [i, 0]
-
y:=अंक[i, 1]
-
साइड :=|points[i,0] - पॉइंट्स[j,0]|
-
-
-
-
my_map [अंक [जे, 0], अंक [जे, 1]]:=my_map [अंक [जे, 0], अंक [जे, 1]] + 1
-
-
my_map [अंक [i, 0], अंक [i, 1]]:=my_map [अंक [i, 0], अंक [i, 1]] + 1
-
-
यदि भुजा -1 के समान नहीं है, तो
-
डिस्प्ले साइड
-
डिस्प्ले पॉइंट (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)
