C++11(clang++ 3.9) 解法, 执行用时: 413ms, 内存消耗: 3412K, 提交时间: 2018-11-22 14:35:50

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

typedef long long LL ;

/******************************************************************************/
struct Tfrac { LL sky , sea ; } ;
Tfrac TfracIS(LL _sky , LL _sea) {
	Tfrac ret ; ret.sky = _sky ; ret.sea = _sea ; return ret ;
}
Tfrac operator +(Tfrac a , Tfrac b) {
	Tfrac c ; c.sea = a.sea * b.sea ; c.sky = a.sky * b.sea + b.sky * a.sea ;
	return c ;
}
Tfrac operator -(Tfrac a , Tfrac b) { b.sky *= -1 ; return a + b ; }
Tfrac operator *(Tfrac a , Tfrac b) { a.sky *= b.sky ; a.sea *= b.sea ; return a ; }
Tfrac operator /(Tfrac a , Tfrac b) { swap(b.sky , b.sea) ; return a * b ; }
bool operator ==(Tfrac a , Tfrac b) { return ((a.sky * b.sea) == (a.sea * b.sky)) ; }
bool operator !=(Tfrac a , Tfrac b) { return ((a.sky * b.sea) != (a.sea * b.sky)) ; }
bool operator <(Tfrac a , Tfrac b) {
	if (a.sea < 0) {a.sea *= -1; a.sky *= -1;}
	if (b.sea < 0) {b.sea *= -1; b.sky *= -1;}
	return ((a.sky * b.sea) < (a.sea * b.sky)) ;
}
bool operator <=(Tfrac a , Tfrac b) {
	return ((a < b) || (a == b)) ;
}
bool operator >(Tfrac a , Tfrac b) { return !(a <= b) ; }
bool operator >=(Tfrac a , Tfrac b) { return !(a < b) ; }
ostream& operator << (ostream& output , Tfrac& c) {
   output << c.sky << "/" << c.sea ;
   return output ;
}
/******************************************************************************/
typedef pair<Tfrac,Tfrac> Tpoint ;
ostream& operator << (ostream& output , Tpoint& c) {
   output << "(" << c.first << "," << c.second << ")" ;
   return output ;
}
Tpoint TpointIS(Tfrac _x , Tfrac _y) {
	Tpoint ret ; ret.first = _x ; ret.second = _y ; return ret ;
}
Tpoint operator -(Tpoint pt1 , Tpoint pt2) {
	pt1.first = pt1.first - pt2.first ;
	pt1.second = pt1.second - pt2.second ;
	return pt1 ;
}
Tfrac CrossProduct(Tpoint pt1 , Tpoint pt2) {
	Tfrac dat = pt1.first * pt2.second - pt1.second * pt2.first ;
	//cerr << "CrossProduct(" << pt1 << "," << pt2 << ")=" << dat << "\n" ;
	return dat ;
}

const int MAXN = 100009 ;

int N ;
Tpoint Pts[MAXN] ;
void Init() {
	LL _s = 0 ;
	for ( int i = 0 ; i < N ; i ++ ) {
		LL _a ; cin >> _a ;
		_s += _a ;
		Pts[i] = TpointIS(TfracIS(_s,1),TfracIS(_s,_a)) ;
		//cerr << Pts[i] << " " ;
	}
	//cerr << "\n" ;
	//for ( int i = 0 ; i < N ; i ++ ) {
	//	Pts[i] = TpointIS(TfracIS(rand()%11,rand()%10+1) , TfracIS(rand() % 11 , rand() % 10 + 1));
	//}
	sort(Pts , Pts+N) ;
	//for ( int i = 0 ; i < N ; i ++ ) cerr << Pts[i] << " " ; cerr << "\n" ;
	//for ( int i = 0 ; i < N ; i ++ ) {
	//	cout << "(" << Pts[i].first << "," << Pts[i].second << ") " ;
	//}
	//cout << "\n" ;
}

Tpoint Stack[MAXN] , ans[MAXN] ;
int tot ;
void Solve() {
	tot = 0 ;
	int t = 1 ; Stack[0] = Pts[0] ;
	for ( int i = 1 ; i < N ; i ++ ) {
		if ( Pts[i] == Pts[i-1] ) continue ;
		while ( t >= 2 && CrossProduct(Pts[i]-Stack[t-2],Stack[t-1]-Stack[t-2]) >= TfracIS(0,1) )
			t -- ;
		Stack[t++] = Pts[i] ;
	}
	for ( int i = 0 ; i < t ; i ++ ) ans[tot++] = Stack[i] ;
	t = 1 ; Stack[0] = Pts[N-1] ;
	for ( int i = N-2 ; i >= 0 ; i -- ) {
		if ( Pts[i] == Pts[i+1] ) continue ;
		while ( t >= 2 && CrossProduct(Pts[i]-Stack[t-2],Stack[t-1]-Stack[t-2]) >= TfracIS(0,1) )
			t -- ;
		Stack[t++] = Pts[i] ;
	}
	for ( int i = 1 ; i < t-1 ; i ++ ) ans[tot++] = Stack[i] ;
	double Area = 0.0 ;
	for ( int i = 0 ; i < tot ; i ++ ) {
		Tfrac tmp = CrossProduct(ans[i] , ans[(i+1)%tot]) ;
		Area += (double)tmp.sky / (double)tmp.sea ;
	}
	cout.precision(5) ;
	cout << fixed << Area *.5 << "\n" ;
}

int main() {
	int Test ; cin >> Test ;
	for ( int i = 1 ; i <= Test ; i ++ ) {
		cin >> N ;
		Init() ;
		Solve() ;
	}
	fprintf(stderr,"%.2f s\n",clock()*1.0/CLOCKS_PER_SEC);
}