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!
