2013腾讯编程马拉松初赛第〇场（3月20日）湫湫系列故事——植树节 HDOJ 4503

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4503

思路：hint from a GOD-COW.

将每一个人模拟成图的一个点，两点连线当且仅当两人是朋友，记这样构造的图为G。根据图G的每一个顶点的度数K，可以算出相对于完全图该点还剩下的度数为：n-k-1

这样，构造图G的补图G~，题目所求相同关系即可以这样理解：要么三个点构成的三角形全部取自图G的边，要么全部取自补图G~中的边，我们算这种情况的逆问题：既有边取自G又有边取自G~的三角形，那么我们可以根据：sum(k*(n-1-k)) 对每一个顶点求和，这样得到的sum/2就是反面情况三角形个数，最后用完全图中三角形的总个数减掉sum可以得到结果。

#include <iostream>                               
#include <algorithm>                              
#include <cstring>  
#include <cstdlib>       
#include <cstdio>  
#include <iomanip>                     
                              
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		double n,sum=0;
		cin>>n;
		double ans=n*(n-1)*(n-2)/6;
		for(int i=0;i<n;i++)
		{
			double x;
			cin>>x;
			sum+=x*(n-1-x);
		}
		sum/=2;
		cout<<fixed<<setprecision(3)<<(ans-sum)/ans<<endl;
	}
	return 0;
}