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.
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 space-separated integers.
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.
- 1 ≤ T ≤ 40000
- 2 ≤ N ≤ 105
- 1 ≤ Value of the array elements ≤ 108
- 1 ≤ Sum of N over all cases ≤ 2*105
Input: 2 3 2 4 1 4 2 4 1 3 Output: 6 13
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
|Tags||acm15kol, convex-hull, devuy11|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.