Algorithm

Problem link- https://www.spoj.com/problems/QUADAREA/

QUADAREA - Maximal Quadrilateral Area

no tags 

 

You are trying to build a house, but unfortunately you currently have only four available walls with side lengths a, b, c, and d. You want your house to be as big as possible, so you would like to know the largest possible area of any quadrilateral you can construct with these four side lengths.

Input

The first line contains the integer T (1 ≤ T ≤ 2,000), the number of tests. Each test contains a single line with four real numbers: a, b, c, and d (0 < a, b, c, d < 1,000). Note that it will always be possible to form a valid quadrilateral with these lengths; that is, the sum of any three side lengths will be strictly larger than the other one.

Output

For each test case, print a single line containing the largest possible area. Your output will be accepted if it is within 0.01 of the official answer.

Example

Input:
2
1 2 1 2
0.5 0.5 0.5 0.5

Output:
2.00
0.25

For the first test case, it is optimal to construct a rectangle, and for the second, a square is optimal.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>

using namespace std;

int main(){
	int t=0;
	double a,b,c,d,s;
	scanf("%d",&t);
	while(t--){
		scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
		s=(a+b+c+d)/2.0;
		printf("%lf\n",sqrt((s-a)*(s-b)*(s-c)*(s-d)));
	}
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
1 2 1 2
0.5 0.5 0.5 0.5

Output

x
–
+
cmd
2.00
0.25

#2 Code Example with Java Programming

Code - Java Programming

import static java.lang.Math.sqrt;
import java.util.Scanner;
class MaximalQuadrilateralArea
{
    public static void main(String[] args)
   {
      Scanner s=new Scanner(System.in);
       int t;
       t=s.nextInt();
       while(t>0)
       {
            double a,b,c,d;
            double area,s1;
            a=s.nextDouble();
            b=s.nextDouble();      
            c=s.nextDouble();
            d=s.nextDouble();
            s1=(a+b+c+d)/2; 
      area=  sqrt((s1-a)*(s1-b)*(s1-c)*(s1-d)) ; 
         System.out.println(area);
         t--;
      }  
   }


}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
1 2 1 2
0.5 0.5 0.5 0.5

Output

x
–
+
cmd
2.00
0.25
Advertisements

Demonstration

SPOJ Solution-Maximal Quadrilateral Area-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python