POI 13rd Warehouse

25-04-10   14:01       Warehouse      OK           100                                                                              .


有趣的題目XD

很神秘的圖片: 圖片

p=1是曼哈頓距離
p=2是歐式距離
p=∞就是這個題目問的問題了，Chebyshev distance



反正這張圖很好用(?


然後會做了還是會有一個盲點，反正很帥的題目˙//˙

//*********************************

#include<algorithm>
int n, i, xx, yy, ax, ay, _x, _y; long long sum, now, t;
struct pl{
	int i,j,c,x,y;
	void get(){
		scanf("%d%d%d", &x, &y, &c);
		sum+= (long long)c;
		i= x+y;
		j= x-y;
	}
}p[100000];
bool cmp(pl a, pl b){return a.i<b.i;}
bool cmp2(pl a, pl b){return a.j<b.j;}
int main(){
	scanf("%d", &n);
	for(i=0; i<n; i++)
		p[i].get();
	std::sort(p, p+n, cmp);
	for(now=0, i=0; i<n; i++){
		now+= (long long)p[i].c;
		if(now> sum/2){
			xx= p[i].i;
			break;
		}
	}
	std::sort(p, p+n, cmp2);
	for(now=0, i=0; i<n; i++){
		now+= (long long)p[i].c;
		if(now> sum/2){
			yy= p[i].j;
			break;
		}
	}
	ax= (xx+yy)/2; ay= (xx-yy)/2;
	for(now=9223372036854775807LL,xx=0; xx<2; xx++)
		for(yy=0; yy<2; yy++){
			int x=ax+xx, y=ay+yy, tx, ty;
			for(t=0,i=0; i<n; i++){
				tx=(x>p[i].x?x-p[i].x:p[i].x-x);
				ty=(y>p[i].y?y-p[i].y:p[i].y-y);
				t+= (long long)(tx>ty?tx:ty)*p[i].c;
			}
			if(t<now){
				now= t;
				_x= x;
				_y= y;
			}
		}
	printf("%d %d\n", _x, _y);
}