# Zoj-3752

The Three Guys

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

Recent days, a joke spread out among Chinese social networks. “If Yao MingGuo Jingming and He Jiong lying on the ground, can they form a triangle?” Some netizens think that it is impossible to form a triangle since Yao Ming is a basketball giant, while Guo Jingming and He Jiong are artists with short statures. But another group of netizens came out and claim: “Yes, they can!” Someone even has presented a sketch to prove their theory:

There are three guys in somewhere of the world. They have learned of this idea and want to try it out by themselves. Given you the height of the three guys, please find out the maximum area of triangle they can form. The height consists of two parts: the upper part of body Ui and the lower part of body Li.

#### Input

There are multiple test cases (about 3000). For each test case: There are three lines. Each line consists of two integers Ui and Li (1 <= Ui, Li <= 150) indicates the height of two parts of the i-th guy.

#### Output

For each test case, output the maximum area of triangle they can form. Any solution with a relative or absolute error of at most 1e-9 will be accepted.

#### Sample Input

10 10
20 20
30 30


#### Sample Output

600.000000000000


Author: JIANG, Kai Source: ZOJ Monthly, January 2014

#### 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

inline double area_triangle(int a,int b,int c){
long q=1L*(a+b+c)*(a+b-c)*(a+c-b)*(b+c-a);//!!3*150^4=1,518,750,000溢出Int！！！ ZOJ int:16 long:32
return sqrt(q)/4.0;
}

inline int is_tri(int a,int b,int c){
return a+b>c && a+c>b && b+c>a;
}

int main(){
int a[4][2],b[6],sum;
int p1[3]={0,1,2};
int p2[3][2]={ {0,1},{0,1},{0,1}};
int a1,a2,a3;
double ans,tmp;
while(~scanf("%d%d %d%d %d%d",&a[0][0],&a[0][1],&a[1][0],&a[1][1],&a[2][0],&a[2][1])){
ans=0;
sum=0;
for(int i=0;i<6;i++){
sum+=a[i>>1][i&1];
}
p1[0]=0,p1[1]=1,p1[2]=2;
do{
//printf("#%d %d %d\n",p1[0],p1[1],p1[2]);
p2[0][0]=0,p2[0][1]=1;
do{
p2[1][0]=0,p2[1][1]=1;
do{
p2[2][0]=0,p2[2][1]=1;
do{
for(int i=0;i<6;i++){
b[i]=a[p1[i>>1]][p2[p1[i>>1]][i&1]];
}
for(int i=0;i<4;i++){
for(int j=i+1;j<5;j++){
for(int k=j+1;k<6;k++){
a2=0,a3=0;
for(int l=i;l<j;l++){
a2+=b[l];
}
for(int l=j;l<k;l++){
a3+=b[l];
}
a1=sum-a2-a3;
if(is_tri(a1,a2,a3)){
tmp=area_triangle(a1,a2,a3);
if(tmp>ans)ans=tmp;
}
}
}
}
}while(next_permutation(p2[2],p2[2]+2)); //前后摆放2种
}while(next_permutation(p2[1],p2[1]+2)); //前后摆放2种
}while(next_permutation(p2[0],p2[0]+2)); //前后摆放2种
}while(next_permutation(p1,p1+3)); //三个人下标排序有3！=6种情况
printf("%.10lf\n",ans);
}
return 0;
}