KGP Summers

All submissions for this problem are available.
Summers in Kharagpur are Hot. And Humid! It’s pretty rough for students who are new to KGP and are not used to the sweating it can cause.
The students want to minimize the amount of sweat while walking from their hostels to class. When they enter the sunshine, they begin sweating. The longer they stay in the sun, the more they sweat.
Precisely, if the Euclidean distance between points A and B is d, then a student sweats d^{2} units when going from A to B without stopping anywhere on the way. But if they stop at a shady spot on the way (like a tree), their continuous sun exposure is broken, and they stop sweating immediately! So they can sit in the shade of the tree and cool off before resuming their journey. Once they leave the shade, they start sweating again.
For example, if a student goes from his room A_{0} to class A_{n+1} while stopping at n trees in between for shade, the total sweat produced is
d(A_{0},A_{1})^{2} + d(A_{1},A_{2})^{2} + …… + d(A_{n},A_{n+1})^{2}
Your task is to help the students find a path from their rooms to class in such a way that they sweat the minimum.
Input
The first line of input contains a single integer T (1 ≤ T ≤ 10), the number of test cases. Then follow the descriptions of the test cases one by one.
For each test case, the first line contains a single integer N (0 ≤ N ≤ 2500) indicating the number of trees on campus. The next N lines each contain a pair of integers denoting the 2D coordinates of each tree. The absolute value of each coordinate is less than or equal to 1000. No two trees have the same location. Then there are 2 additional lines – the coordinates of the student’s room and the classroom respectively.
Output
Print a single integer for each test case on a line by itself, the minimum amount of sweat that should be expended when a student goes from his room to class.
Example
Input: 2 6 8 2 4 0 8 0 4 1 7 1 6 2 2 1 9 2 1 0 0 1 1 1 1 Output: 20 4
Author:  iitgfaculties 
Tags  iitgfaculties 
Date Added:  2112012 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 