How to decrease the time taken for this question's code?

Question

Given n points A[1..n] in the 2-D plane, where i-th point has two attributes A[i].x and A[i].y representing x-coordinate and y-coordinate. Find 3 points A[i], A[j], A[k] (i, j, k are distinct) such that distance(A[i], A[j]) + distance(A[j], A[k]) + distance(A[k], A[i]) is minimized. Here distance(A[i], A[j]) means the Euclid Distance, which is equals to sqrt( (A[i].x - A[j].x)^2 + (A[i].y - A[j].y)^2). You need to output the minimum possible distance.

Input: The first line contains an integer T indicating the number of test cases.

Each test case starts with a positive integer n indicating the number of points.

The following n lines contain two real numbers A[i].x and A[i].y with at-most 6 digits after decimal point describing the coordinates of the point.

Output: T lines in total. Each line starts with "Case #: " and followed by minimum length. Here "#" is the number of the test case starting from 1.

Answers within an absolute or relative error of 10^-6 will be accepted.

Constraints:

• 1 ≤ T ≤ 10
• 3 ≤ n ≤ 100000
• 0 ≤ A[i].x, A[i].y ≤ 10000
• A[i].x, A[i].y are real numbers with atmost 6 digits after decimal position.

Example Input:

1
4
0.0 0.0
2.0 2.0
2.0 0.0
1.0 1.0

Example Output:

Case 1: 4.8284271247

Explanation One possible solution is to select these 3 points (0, 0), (2, 0), (1, 1), the length is sqrt(2) + sqrt(2) + 2

from math import sqrt as s

class Point():
   def __init__(self,x,y):
      self.x = x
      self.y = y


def bruteforce(p):
    d = []
    q=len(p)
    for i in range(q):
        j=i+1
        while j<q:
            temp = s((p[j].x - p[i].x) * (p[j].x - p[i].x) + (p[j].y - p[i].y) * (p[j].y - p[i].y))
            d.append(temp)
    d.sort()
    return (d[0]+d[1]+d[2])

def solution():
  t = int(input())
  for i in range(t):
     temp = 0
     n = int(input())
     p = []
     for j in range(n):
        a, b = map(float, input().split())
        temp = Point(a, b)
        p.append(temp)
  return(bruteforce(p))

print(solution())

What shall I do to decrease the time complexity? Anyone please help me!