zoj-3752

Recent days, a joke spread out among Chinese social networks. “If Yao Ming, Guo 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 U_i and the lower part of body L_i.

Input

There are multiple test cases (about 3000). For each test case:

There are three lines. Each line consists of two integers U_i and L_i (1 <= U_i, L_i <= 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

题意解释：

额，不想具体多说，转换一下，三段可以折叠的木棍，组成面积最大的三角形。由于很久没有做过zoj了，昨天想去看看zoj的月赛，结果悲催的没做出来。赛后调试发现double就可以过，int就不行，这才发现zoj的int是16位整数，而long才是32位整数，不像不像cf的int直接就是32位的，刚刚开始想错了边长是\((150 \times 2)=300\)，而不是我以为的150，故计算过程是超过32位int了的，顺便说一句zoj的long和long long是一样的都是64位整数，不想其他的long和int一样，不过最好不要使用long，因为按照标准int<=long<=long long即可以，那么long取4或者8都是合理的。解法很多，如果思维足够缜密，那么用if是可以写出来的，\(3！*2^3*20=4320\)种情况，但是真的用if应该小于这么多情况。另外就是排列组合的生成了，可以递归也可以while写。

代码

#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 %dn",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("%.10lfn",ans);
	}
	return 0;
}