Save The Trees

All submissions for this problem are available.
CodeChef has been very busy with his christmas preparations and he doesn't have time to look after Samosa Bhai and Jalebi Bai. To keep them busy, CodeChef has given them an array A of size N. He has asked them to plant trees at the points with Cartesian coordinates (A[ i ], A[ j ]), such that i < j.
There are a lot of giraffes nearby. To save the trees from the giraffes, they decide to build a fence around the trees. Moreover, they want to use the minimum length of fencing for this task. Find the value equal to twice the area covered by the fence using the minimum length of fencing.
Input
The first line contains T, the number of test cases to follow.
The first line of each test case contains an integer N, the size of the array.
The second line of the test case contains N spaceseparated integers.
Output
For each test case, output the value equal to two times the area, rounded to the nearest integer, surrounded by the fence when using the minimum length of net to surround all the trees.
Constraints
 1 ≤ T ≤ 40000
 2 ≤ N ≤ 10^{5}
 1 ≤ Value of the array elements ≤ 10^{8}
 1 ≤ Sum of N over all cases ≤ 2*10^{5}
Example
Input: 2 3 2 4 1 4 2 4 1 3 Output: 6 13
Explanation
Example case 1.
Covered portion is a right angled triangle with vertices (2,4), (2,1) and (4,1).
Area = (1/2)*2*3 = 3.
Example case 2.
A, B, C, D, E, and F denote the trees.
The above image denotes the situation.
Area of the figure = 6.5
2*(Area of Triangle ABC + Area of Triangle BFE + Area of Square EFCD) is the answer.
Area of Triangle ABC = 1.5
Area of Triangle BFE = 1
Area of Square EFCD = 2*2 = 4
Author:  devuy11 
Editorial  http://discuss.codechef.com/problems/KOL1509 
Tags  acm15kol, convexhull, devuy11 
Date Added:  18122015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
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. 