2015
05-24

# Quadrilateral

One day the little Jack is playing a game with four crabsticks. The game is simple, he want to make all the four crabsticks to be a quadrilateral, which has the biggest area in all the possible ways. But Jack’s math is so bad, he doesn’t know how to do it, can you help him using your excellent programming skills?

The first line contains an integer N (1 <= N <= 10000) which indicates the number of test cases. The next N lines contain 4 integers a, b, c, d, indicating the length of the crabsticks.(1 <= a, b, c, d <= 1000)

The first line contains an integer N (1 <= N <= 10000) which indicates the number of test cases. The next N lines contain 4 integers a, b, c, d, indicating the length of the crabsticks.(1 <= a, b, c, d <= 1000)

2
1 1 1 1
1 2 3 4

Case 1: 1.000000
Case 2: 4.898979

还有这题还有一个结论，后来才知道的。len是周长的二分之一。area=sqrt((len-a)*(len-b)*(len-c)*(len-d));

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-7
const double pi=acos(-1.0);
typedef long long LL;
const int Max=10100;
const int INF=1000000007;

double num[4];
int t;
double getarea(double a,double b,double c)
{
double all=(a+b+c)/2.0;
return sqrt(all*(all-a)*(all-b)*(all-c));
}
double solve(double a,double b,double c,double d)
{
double left=max(b-a,d-c);
double right=min(a+b,c+d);
while(abs(right-left)>eps)
{
double mid=(right+left)/2.0;
double midright=(mid+right)/2.0;
if(getarea(a,b,mid)+getarea(c,d,mid)>getarea(a,b,midright)+getarea(c,d,midright))
right=midright;
else
left=mid;
}
return getarea(a,b,left)+getarea(c,d,left);
}
int main()
{
cin>>t;
int  kk=1;
while(t--)
{
for(int i=0; i<4; i++)
scanf("%lf",num+i);
if(num[0]>=num[1]+num[2]+num[3]||num[1]>=num[0]+num[2]+num[3]||
num[2]>=num[1]+num[0]+num[3]||num[3]>=num[1]+num[2]+num[0])
{
printf("Case %d: -1\n",kk++);
continue;
}
double ans=0;
sort(num,num+4);
ans=max(ans,solve(num[0],num[1],num[2],num[3]));
ans=max(ans,solve(num[0],num[2],num[1],num[3]));
ans=max(ans,solve(num[0],num[3],num[1],num[2]));
printf("Case %d: %.6lf\n",kk++,ans);

}
return 0;
}


1. 本来以为是彗尾，你这么一说，到的确有道理！这么长的直线，不是彗尾，有可能真是射线，给太阳治病，或者是摧毁太阳上的建筑？