ধরা যাক n জোড়া পয়েন্ট দেওয়া আছে। আমাদের চারটি পয়েন্ট বের করতে হবে যাতে সেগুলো x এবং y অক্ষের সমান্তরাল একটি বর্গ তৈরি করে। যদি সম্ভব না হয় তবে "not possible" রিটার্ন করুন। একাধিক বর্গ থাকলে সর্বোচ্চ ক্ষেত্রফল বিশিষ্টটি বেছে নিন।
ইনপুট: n=6, points=[(2,2),(5,5),(4,5),(5,4),(2,5),(5,2)] → আউটপুট: সাইড ৩, পয়েন্ট: (2,2) (5,2) (2,5) (5,5)।
সমাধানের ধাপসমূহ (হ্যাশ ম্যাপ + ডাবল লুপ)
- my_map: পয়েন্ট -> কাউন্ট ম্যাপ
- side=-1, x=-1, y=-1
- for i in 0..n-1:
- my_map[points[i]]--
- for j in 0..n-1:
- my_map[points[j]]--
- যদি i!=j এবং (points[i].x - points[j].x) == (points[i].y - points[j].y):
- যদি my_map[(points[i].x, points[j].y)]>0 এবং my_map[(points[j].x, points[i].y)]>0:
- যদি side < abs(dx) বা (side==abs(dx) এবং দূরত্ব কম): x,y,side আপডেট
- যদি my_map[(points[i].x, points[j].y)]>0 এবং my_map[(points[j].x, points[i].y)]>0:
- my_map[points[j]]++
- my_map[points[i]]++
- যদি side != -1: প্রিন্ট করুন, অন্যথায় "No such square"
উদাহরণ
def get_square_points(points, n):
my_map = {}
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.get((points[i][0], points[j][1]), 0) > 0 and my_map.get((points[j][0], points[i][1]), 0) > 0:
if side < abs(points[i][0]-points[j][0]) or (side == abs(points[i][0]-points[j][0]) and (points[i][0]**2+points[i][1]**2) < (x**2+y**2)):
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)
