首页 > 代码库 > hdu4386(求四边形最大面积)
hdu4386(求四边形最大面积)
题意:给出一个四边形的边长,求四边形最大面积。不合法输出-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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。