音乐培训如何做网站宣传,网站域名怎么选择,百度xml网站地图,网站模板后台正题
题目链接:https://www.luogu.com.cn/problem/P3964 题目大意
给出nnn个点#xff0c;求一个点使得它到所有点的切比雪夫距离和最小。 0≤n≤105,−109≤xi,yi≤1090\leq n\leq 10^5,-10^9\leq x_i,y_i\leq 10^90≤n≤105,−109≤xi,yi≤109 解题思路
额切比雪夫距…正题
题目链接:https://www.luogu.com.cn/problem/P3964 题目大意
给出nnn个点求一个点使得它到所有点的切比雪夫距离和最小。
0≤n≤105,−109≤xi,yi≤1090\leq n\leq 10^5,-10^9\leq x_i,y_i\leq 10^90≤n≤105,−109≤xi,yi≤109 解题思路
额切比雪夫距离看起来舒服实则难搞因为其实是横纵坐标距离的最大值然后还得求和
所以我们可以转成曼哈顿的就是把(x,y)(x,y)(x,y)变成(xy2,x−y2)(\frac{xy}{2},\frac{x-y}{2})(2xy,2x−y)
然后每个点的横纵坐标分开算距离求和就可以知道每个点的答案了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
ll n,x[N],y[N],p[N],s[N];
bool cmpx(ll a,ll b)
{return x[a]x[b];}
bool cmpy(ll a,ll b)
{return y[a]y[b];}
signed main()
{scanf(%lld,n);ll px0,sx0,py0,sy0;for(ll i1;in;i){ll X,Y;scanf(%lld%lld,X,Y);x[i]XY;y[i]X-Y;sxx[i];syy[i];p[i]i;}sort(p1,p1n,cmpx);for(ll i1;in;i){sx-x[p[i]];s[p[i]]sx-x[p[i]]*(n-i)x[p[i]]*(i-1)-px;pxx[p[i]];}sort(p1,p1n,cmpy);for(ll i1;in;i){sy-y[p[i]];s[p[i]]sy-y[p[i]]*(n-i)y[p[i]]*(i-1)-py;pyy[p[i]];}ll ans1e18;for(ll i1;in;i)ansmin(ans,s[i]);printf(%lld\n,ans/2ll);return 0;
}
