BZOJ 3170 & 切比雪夫距离

时间：2023-03-09 06:09:50
BZOJ 3170 & 切比雪夫距离

题意:

　　给出N个点,在这N个点中选一个点使其它的点与这个点的切比雪夫距离和最小.

SOL:

　　TJOI真是...厚道还是防水...这种题目如果知道切比雪夫距离是什么那不就是傻逼题...如果不知道那不就懵逼了么...

　　与随意选点不同,这种给定点中选与x,y轴还是有一定关系的.所以我们要像树上搞那什么最小距离一样搞这种东西.然后就....

CODE:

　　

/*==========================================================================

# Last modified: 2016-03-04 19:52

# Filename:		3170.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm> 

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector> 

#define lowbit(x) (x)&(-x)

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1] 

#define maxn 130000

#define maxm 130000

#define pi 3.1415926535898

#define _e 2.718281828459

#define INF 1070000000

using namespace std;

typedef long long ll;

typedef unsigned long long ull; 

template<class T> inline

void read(T& num) {

    bool start=false,neg=false;

    char c;

    num=0;

    while((c=getchar())!=EOF) {

        if(c=='-') start=neg=true;

        else if(c>='0' && c<='9') {

            start=true;

            num=num*10+c-'0';

        } else if(start) break;

    }

    if(neg) num=-num;

}

/*==================split line==================*/

struct Infor{

	double x,y;

	int id;

}p[maxn];

double ans[maxn];

int cmpx(Infor a,Infor b){return a.x<b.x;}

int cmpy(Infor a,Infor b){return a.y<b.y;}

int main(){

	int n; read(n);

	double sumx=0,sumy=0;

	FORP(i,1,n) {

		double x,y;

		scanf("%lf%lf",&x,&y);

		p[i].x=(x+y)/2.0;	p[i].y=(x-y)/2.0;

		p[i].id=i;

		sumx+=p[i].x; sumy+=p[i].y;

	}

	sort(p+1,p+1+n,cmpx);

	double temp=0;

	FORP(i,1,n){

		//int t=p[i].x-p[i-1].x;

		ans[p[i].id]+=((i-1)*p[i].x)-temp;

		ans[p[i].id]-=((n-i+1)*p[i].x-(sumx-temp));

		temp+=p[i].x;

	}

	sort(p+1,p+1+n,cmpy);

	temp=0;

	FORP(i,1,n){

		ans[p[i].id]+=(i-1)*p[i].y-temp;

		ans[p[i].id]-=((n-i+1)*p[i].y-(sumy-temp));

		temp+=p[i].y;

	}

	double out=ans[1];

	FORP(i,1,n) out=min(out,ans[i]);

	printf("%.0lf\n",out);

}

相关文章