YJQQQAQ's Blog

题解：

    （此题据说是TJ省选题？不是提高组么）

     先转45°，然后顺手就可以A了，我用的线段树统计的答案，统计的方法是直接用max(abs(x[i]-x[j]),abs(y[i]-y[j]))的公式，枚举一个点作为中点，然后把平面分成4块，分块统计（妥了），注意边界问题

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <cstdlib>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
const int MAXN = 100010;
int n;
struct NODE {
		int l,r,sum;
		long long sumx,sumy;
} seg[MAXN << 2];

struct POINT {
		int x,y,lab,a,b;
		void read() {
				scanf("%d%d",&x,&y);
				a = y-x;
				b = y+x;
		}
} pnts[MAXN];

int pos[MAXN];

struct OPT {
		int v,lab;
		bool operator < (const OPT another) const {
				return v < another.v;
		}
} opt[MAXN];
int pc(0);
void Uni() {
		sort(opt+1,opt+n+1);
		for (int i=1;i<=n;i++) {
				if ((opt[i].v != opt[i-1].v) || (i == 1)) pos[opt[i].lab] = ++pc;
				else pos[opt[i].lab] = pc;
		}
}

bool cmp(POINT p1,POINT p2) {
		return p1.b < p2.b;
}

void build(int x,int l,int r) {
		seg[x].l = l;
		seg[x].r =r ;
		seg[x].sumx= seg[x].sumy = seg[x].sum = 0;
		if (l == r) return;
		int mid = (l + r)>> 1;
		build(x << 1,l,mid);
		build((x << 1) + 1,mid+1,r);
}


void modify(int x,int p,int a,int b) {
		if (seg[x].l == seg[x].r) {
				seg[x].sum ++;
				seg[x].sumx += a;
				seg[x].sumy += b;
				return;
		}
		int mid = (seg[x].l + seg[x].r) >> 1;
		if (p <= mid) modify(x << 1,p,a,b);
		else modify((x << 1) + 1,p,a,b);
		seg[x].sum = seg[x << 1].sum + seg[(x << 1) + 1].sum;
		seg[x].sumx = seg[x << 1].sumx + seg[(x << 1) + 1].sumx;
		seg[x].sumy = seg[x << 1].sumy + seg[(x << 1) + 1].sumy;
}

void merge(NODE &s,NODE s1,NODE s2) {
		s.sum = s1.sum + s2.sum;
		s.sumx = s1.sumx + s2.sumx;
		s.sumy = s1.sumy + s2.sumy;
}
NODE query(int x,int l,int r) {
		if (seg[x].l == l && seg[x].r == r) return seg[x];
		int mid = (seg[x].l + seg[x].r) >> 1;
		if (r <= mid) return query(x << 1,l,r);
		if (l > mid) return query((x << 1) + 1,l,r);
		NODE s;
		merge(s,query(x << 1,l,mid),query((x << 1) + 1,mid+1,r));
		return s;
}

long long ret[MAXN];
int main() {
		scanf("%d",&n);
		for (int i=1;i<=n;i++) {
				pnts[i].read();
				pnts[i].lab = i;
				opt[i].v = pnts[i].a;
				opt[i].lab = i;
		}
		Uni();
		sort(pnts+1,pnts+1+n,cmp);
	//	for (int i=1;i<=n;i++) {
	//			printf("%d %d\n",pnts[i].x,pnts[i].y);
	//	}
		build(1,0,pc);
		for (int i=1;i<=n;i++) {
				int cur = pnts[i].lab;
				int p = pos[cur];
				NODE s = query(1,p,pc);
				ret[cur] += (long long) pnts[i].x * (long long)s.sum - s.sumx;
				s = query(1,0,p-1);
				ret[cur] += (long long) pnts[i].y * (long long)s.sum - s.sumy;
				modify(1,p,pnts[i].x,pnts[i].y);
		}
		build(1,0,pc);
		for (int i=n;i;i--) {
				int cur = pnts[i].lab;
				int p = pos[cur];
				NODE s = query(1,0,p-1);
				ret[cur] +=  s.sumx - (long long) pnts[i].x * (long long)s.sum;
				s = query(1,p,pc);
				ret[cur] += s.sumy - (long long) pnts[i].y * (long long)s.sum;
				modify(1,p,pnts[i].x,pnts[i].y);
		}
		long long ans = ret[1];
		for (int i=2;i<=n;i++) {
				if (ret[i] < ans) {
						ans = ret[i];
				}
		}
		printf(LL "\n",ans);
}