ABC178 E - Dist Max-白红宇的个人博客

ABC178 E - Dist Max

发布日期：2021-05-14 16:53:28 浏览次数：22 分类：精选文章

本文共 729 字，大约阅读时间需要 2 分钟。

在这里插入图片描述

题意很简单：求平面所有点最大的曼哈顿距离。

｜xi - xj | + | yi - yj | 的最大值。

思路：

假设 xi > xj ，那么yi 和 yj 有两种情况， yi大于yj的时候

即 ( xi - yi ) - ( xj - yj) 的最大值，反之 (xi + yi) - (xj + yj)的最大值，我们记录这两个值就行了。最后取max。

#include
   
    #include
    
     #include
     
      #include
      
       #define x first#define y secondusing namespace std;const int N=200010;struct node{       int x;    int y;    int id;    bool operator < (const node & W)const    {           if(x!=W.x)        return x

v;int get(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}int main(){ cin >> n; for(int i=1;i<=n;i++) { int x,y; cin >> x >>y; b[i]=x-y,c[i]=x+y; } sort(b+1,b+1+n),sort(c+1,c+1+n); cout<

上一篇：张老师的旅行区间dp

下一篇：AtCoder Beginner Contest 179

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章