---{"category_name":"easy","problem_code":"KOL1509","problem_name":"Save The Trees","languages_supported":{"0":"C","1":"CPP14","2":"JAVA"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"devuy11","problem_tester":null,"date_added":"18-12-2015","tags":{"0":"acm15kol","1":"convex","2":"devuy11"},"editorial_url":"http://discuss.codechef.com/problems/KOL1509","time":{"view_start_date":1451123700,"submit_start_date":1451123700,"visible_start_date":1451123700,"end_date":1735669800},"layout":"problem"}---<span class="solution-visible-txt">All submissions for this problem are available.</span><p>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 <b>A</b> of size <b>N</b>. He has asked them to plant trees at the points with Cartesian coordinates (<b>A[ i ]</b>, <b>A[ j ]</b>), such that <b>i</b> < <b>j</b>.</p><p>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 <b>twice the area</b> covered by the fence using the minimum length of fencing.</p><h3>Input</h3><p>The first line contains <b>T</b>, the number of test cases to follow.</p><p>The first line of each test case contains an integer <b>N</b>, the size of the array.</p><p>The second line of the test case contains <b>N</b> space-separated integers.</p><h3>Output</h3><p>For each test case, output the value equal to <b>two times the area</b>, rounded to the nearest integer, surrounded by the fence when using the minimum length of net to surround all the trees.</p><h3>Constraints</h3><ul><li><b>1</b> ≤ <b>T</b> ≤ <b>40000</b></li><li><b>2</b> ≤ <b>N</b> ≤ <b>10<sup>5</sup></b></li><li><b>1</b> ≤ <b>Value of the array elements</b> ≤ <b>10<sup>8</sup></b></li><li><b>1</b> ≤ <b>Sum of N over all cases</b> ≤ <b>2*10<sup>5</sup></b></li></ul><h3>Example</h3><pre><b>Input:</b>232 4 142 4 1 3<b>Output:</b>613</pre><h3>Explanation</h3><p><b>Example case 1.</b><br>Covered portion is a right angled triangle with vertices (2,4), (2,1) and (4,1).<br>Area = (1/2)*2*3 = 3.</p><p><b>Example case 2.</b><img src="https://www.codechef.com/download/ACM15KOL/export.png"></img><br/>A, B, C, D, E, and F denote the trees.<br/>The above image denotes the situation.<br/>Area of the figure = 6.5<br/>2*(Area of Triangle ABC + Area of Triangle BFE + Area of Square EFCD) is the answer.<br/>Area of Triangle ABC = 1.5<br/>Area of Triangle BFE = 1<br/>Area of Square EFCD = 2*2 = 4<br/></p>