AA-VV Plan a Holiday!
AA: "I'm tired "
AA: "I'm tired of this daily hustle and bustle "
AA: "I'm tired of you , your jokes and all your crap"
AA: "I'm tired of life "
AA: "I need a break!"
This is a snippet from a recent conversation between BFF's AA and VV , who are now planning on a holiday . VV , being as cool as he can , and trying to make the best of this holiday , plans a road trip . They hire a car , and jot down certain destinations to visit . They want to visit all destinations . You need to help AA-VV plan their holiday.
You are given N destinations , represented as coordinates on a 2D plane . You need to plan out a trip such that it visits all destinations . There is just one fuel station in the entire region , which is the starting point . The maximum distance that the car can travel without refuelling is of 2 destinations, i.e it has to come back to its starting point after travelling a maximum of 2 destinations . You need to plan the holiday in such a way that it takes minimum time . The time taken to go from one point to another is the sqaure of the euclidean distance between them .
Given T test cases . T <= 50
Now each test case consists of Sx,Sy (their starting coordinates) .
The next line consists of N , the number of destinations . N <= 17
Followed by N lines , containing coordinates of destinations .
Output the minimum time taken to cover all destinations .
(Integer i , represents the ith point : 0: starting base )
Test Case 1 :
0 1 2 0
Test case 2 :
0 1 2 0 3 0
Problem Setter : Akshit Poddar