ZOJ - 3752 The Three Guys

题意：求三个人能组成的最大的三角形面积，人是可以折叠的

思路：设想三个人六个点围成一个圆，按要求选出三个点，如果可以组成三角形的话，就求他们的面积，当然人是不能拆开的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

double area(int a,int b,int c){
	if (a < b+c && a > abs(b-c)){
		double p = (a+b+c)/2.0;
		return sqrt(p*(p-a)*(p-b)*(p-c));
	}
	return 0;
}

double solve(int a[]){
	int sum = 0;
	for (int i = 1; i <= 6; i++)
		sum += a[i];
	double ans = 0,tmp;
	for (int i = 1; i <= 6; i++)
		for (int j = i+1; j <= 6; j++)
			for (int k = j+1; k <= 6; k++){
				int x = 0,y = 0,z = 0;
				for (int l = i+1; l <= j; l++)
					x += a[l];
				for (int l = j+1; l <= k; l++)
					y += a[l];
				z = sum - x - y;
				ans = max(ans,area(x,y,z));
			}
	return ans;
}

int main(){
	int a[10],b[10];
	while (scanf("%d",&a[1]) != EOF){
		for (int i = 2; i <= 6; i++)
			scanf("%d",&a[i]);
		int c[10] = {0,1,2,3,4,5,6};
		double ans = 0,tmp;
		do{
			int flag = 0;
			for (int i = 1; i <= 6; i += 2)
				if (abs(c[i]-c[i+1]) != 1){
					flag = 1;
					break;
				}
			if (flag)
				continue;
			for (int i = 1; i <= 6; i++)
				b[i] = a[c[i]];
			tmp = solve(b);
			if (tmp > ans)
				ans = tmp;
		}while (next_permutation(c+1,c+7));
		printf("%.12lf\n",ans);
	}
	return 0;
}

ZOJ - 3752 The Three Guys,布布扣,bubuko.com

ZOJ - 3752 The Three Guys

原文：http://blog.csdn.net/u011345136/article/details/20840321