感觉自己直接暴力枚举三条边的做法真是丑哭了。
dfs生成组合,然后计算面积。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include<ctype.h> #include<map> #include<time.h> #include<bitset> using namespace std; //hdu 5135 const int maxn=13; int N; double len[maxn]; int ed; int g[4][3]; double ans; bool used[maxn]; bool judge(double a,double b,double c) { if(a<(b+c)&&b<(a+c)&&c<(a+b)) { if(a>abs(b-c)&&b>abs(a-c)&&c>abs(a-b)) { //cout<<a<<" "<<b<<" "<<c<<endl; return true; } } return false; } double area(double a,double b,double c) { double h=(a+b+c)/2.0; double s=sqrt(h*(h-a)*(h-b)*(h-c));//三角形面积的海伦公式 return s; } void cal() { double ar=0; for(int i=0;i<ed;i++) { int x=g[i][0]; int y=g[i][1]; int z=g[i][2]; double a=len[x]; double b=len[y]; double c=len[z]; if(judge(a,b,c)) { ar+=area(a,b,c); } } ans=max(ans,ar); } int dep; void dfs(int x,int y,int begin) { if(x>=ed) { cal(); // for(int i=0;i<ed;i++) // { // for(int j=0;j<3;j++) // { // cout<<g[i][j]<<" "; // } // } // cout<<endl; // cout<<(dep++)<<endl; return; } if(y>=3) { dfs(x+1,0,1); } else { for(int i=begin;i<=N;i++) { if(used[i]==1) continue; g[x][y]=i; //cout<<"set: "<<x<<" "<<y<<" "<<g[x][y]<<endl; used[i]=1; dfs(x,y+1,i+1); used[i]=0; } } } int main() { freopen("input.txt","r",stdin); //freopen("data.txt","r",stdin); //freopen("out1.txt","w",stdout); while(true) { scanf("%d",&N); if(N==0) { break; } ed=N/3; for(int i=1;i<=N;i++) { scanf("%lf",&len[i]); } memset(used,0,sizeof(used)); ans=0; dfs(0,0,1); printf("%.2lf\n",ans); } return 0; }