2926.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2926  User Id:fzk 
Memory:3972K  Time:1278MS
Language:C++  Result:Accepted

Source 

#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
using namespace std;

double x[100000][5];

int main( ) {
	int n, i, k, j;
	int sign[5];
	double best = 0, min, max, t;
	scanf( "%d", &n );
	
	for( i=0; i<n; i++ )
		scanf( "%lf%lf%lf%lf%lf", x[i], x[i]+1, x[i]+2, x[i]+3, x[i]+4 );
		
	for( k=0; k<32; k++ ) {
		for( i=0; i<5; i++ )
			sign[i] = (k&(1<<i)) ? 1 : -1;
		min = 1e100, max = -1e100;
		for( i=0; i<n; i++ ) {
			t = 0;
			for( j=0; j<5; j++ )
				t += sign[j]*x[i][j];
			if( t > max )
				max = t;
			if( t < min )
				min = t;
		}
		if( max-min > best )
			best = max-min;
	}
	printf( "%.2lf\n", best );
	return 0;
}