学步园

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2688

题意：给定N(N <= 1e5)个点，求两点之间的最大曼哈顿距离；

分析：由二维的曼哈顿距离可知：dis(p1,p2) = abs(x1-x2) + abs(y1-y2) ；

则dis(p1,p2) = max{(x1+y1) - (x2+y2) , (x1-y1) - (x2-y2) , (-x1+y1) - (-x2+y2)  , (-x1-y1) - (-x2-y2) } ；

因此只需要判断两个最远点之间的2^k个距离中的最大值就是所要求的值，这里k是点的维数。

时间复杂度为O(N*2^K) ;

代码：

/*
ZOJ 2688 Requirements
Tips : dfs + 曼哈顿距离； 
*/
#include<stdio.h>
int N;
double data[6] ;
double myh[100001][33] ;
int ch[6] ;
void dfs(int start,int i,int index){
	if(start == 6){
		double res = 0 ;
		for(int j=1;j<=5;j++){
			res += data[j]*ch[j] ;	
		}	
		myh[i][index] = res ;
		return ;
	}
	ch[start] = -1; 
	dfs(start+1,i,index*2) ;	//第start个元素取-1 
	ch[start] = 1  ;
	dfs(start+1,i,index*2+1);	//第start个元素取1 ； 
}
int main()
{
	while(scanf("%d",&N) && N)
	{
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=5;j++)
			{
				scanf("%lf",&data[j]);	
			}
			dfs(1,i,0);
		}	
		double maxi = 0 ;
		for(int i=0;i<32;i++)
		{
			double min_ = myh[1][i] ;
			double max_ = myh[1][i] ;
			
			for(int j=2;j<=N;j++){
				if(myh[j][i] < min_ )	min_ = myh[j][i] ;
				if(myh[j][i] > max_ )	max_ = myh[j][i] ;	
			}	
			if(maxi < max_ - min_ )
				maxi = max_ - min_ ;
		}
		printf("%.2f\n",maxi);
	}	
	return 0;	
}