मान लीजिए हमारे पास n जोड़ी बिंदु हैं; हमें चार बिंदु ढूंढने हैं ताकि वे एक वर्ग उत्पन्न कर सकें जिसकी भुजाएं x और y अक्ष के समानांतर हों अन्यथा "not possible" वापस करें। यदि हम एक से अधिक वर्ग ढूंढ सकते हैं तो उसको चुनें जिसका क्षेत्रफल अधिकतम हो।
तो, यदि इनपुट 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) प्रदर्शित करें
अन्यथा,
"No such square" प्रदर्शित करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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)
