solution : School of Geometry | codechef problem | problem code : SNUG_FIT

codechef probelm :

problem code : SNUG_FIT

Once again, we have a lot of requests from coders for a challenging problem on geometry. Geometry expert Nitin is thinking about a problem with parabolas, icosahedrons, crescents and trapezoids, but for now, to encourage beginners, he chooses to work with circles and rectangles.

You are given two sequences A1,A2,…,AN$A_1,A_2,\dots ,A_N$ and B1,B2,…,BN$B_1,B_2,\dots ,B_N$. You should choose a permutation P1,P2,…,PN$P_1,P_2,\dots ,P_N$ of the integers 1$1$ through N$N$ and construct N$N$ rectangles with dimensions A1×BP1,A2×BP2,…,AN×BPN$A_1\times B_{P_1},A_2\times B_{P_2},\dots ,A_N\times B_{P_N}$. Then, for each of these rectangles, you should construct an inscribed circle, i.e. a circle with the maximum possible area that is completely contained in that rectangle.

Let S$S$ be the sum of diameters of these N$N$ circles. Your task is to find the maximum value of S$S$.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.
• The third line contains N$N$ space-separated integers B1,B2,…,BN$B_1,B_2,\dots ,B_N$.

Output

For each test case, print a single line containing one integer ― the maximum value of S$S$. It is guaranteed that this value is always an integer.

Constraints

• 1≤T≤50$1\le T\le 50$
• 1≤N≤104$1\le N\le {10}^4$
• 1≤Ai,Bi≤109$1\le A_i,B_i\le {10}^9$ for each valid i$i$

Subtasks

Subtask #1 (20 points):

• A1=A2=…=AN$A_1=A_2=\dots =A_N$
• B1=B2=…=BN$B_1=B_2=\dots =B_N$

Subtask #2 (80 points): original constraints

Sample Input 1 

2
4
8 8 10 12
15 20 3 5
3
20 20 20
10 10 10

Sample Output 1 

30
30

Explanation

Example case 1: Four rectangles with dimensions 8×3$8\times 3$, 8×5$8\times 5$, 10×20$10\times 20$ and 12×15$12\times 15$ lead to an optimal answer.

solution : 

 #include <bits/stdc++.h>

using namespace std;

int main() {

int t;

cin >> t;

while(t--)

{

    int n ;

    cin >> n;

    int a[100000];

    int b[100000];

    for(int i =0 ; i < n ; i++)

    {

        cin >> a[i];

    }

    for(int i =0 ; i < n ; i++)

    {

        cin >> b[i];

    }

    sort(a , a+n);

    sort(b , b+n);

    long int sum_dia =0;

    for(int i =0 ; i < n ; i++)

    {

        sum_dia += (b[i]<a[i]?b[i]:a[i]);

        

    }

    cout << sum_dia << "\n";

}

return 0;

}