首页 > ACM题库 > HDU-杭电 > HDU 4386-Quadrilateral-计算几何-[解题报告]HOJ
2015
05-24

HDU 4386-Quadrilateral-计算几何-[解题报告]HOJ

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

题意:给出一个四边形的边长,求四边形最大面积。不合法输出-1;


解法:比较明显的三分,先枚举四边形的边的连接,然后三分一个对角线长度。但是比较怪异的是eps取1e-8wa了,去1e-7才可以过。不知道谁可以解释一下。

          还有这题还有一个结论,后来才知道的。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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xiefubao/article/details/25877221