11.7 T3.B

这几天的题最后一道基本都不是压轴题

分析：

题解寥寥数语，但是蕴含了古今之道

首先我们看到了一个函数式：|u-x|+|v-y|

实践出真知，所以我们先试图画出这个斜正方形：

具体画法：定住x，确定y的范围；定住y，确定x的范围

如图所示，我们得到的是一个完美的正方形，就是有点斜，并且四个顶点以及中点都是由规律的

如题解所说，我们现在需要旋转这个正方形：在平面中确定一个矩形，我们只要用两个点就可以了，所以我们的旋转也只涉及两个点（这样简化了计算）

我们选择这两个红色的点旋转

现在我们选择一个旋转中心（原点就可以了）

这里就要涉及向量旋转的知识了

向量(x,y)绕起点逆时针旋转a弧度，得到的点坐标为(x*cosa-y*sina , x*sina+y*cosa)

因为等比例扩大矩形，对于相交的结果是没有影响的，所以我们可以把前面的系数都去掉

矩形的交只要维护四个极限边界值即可：

最靠右的左边界，最靠左的右边界

最靠上的下边界，最靠下的上边界

（仔细体会一下）

//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

const int INF=;
const int N=;
int n,m,maxx=;
struct node{
    int x,y;
    bool operator < (const node &a) const
    {
        return x<a.x;
    }
};
node po[N];

node make(int x,int y)
{
    return (node){x-y,x+y};
}

int pd(int len)
{
    int lx=-INF,rx=INF,ly=-INF,ry=INF;
    for (int i=;i<=m;i++)
    {
        if (po[i].y-po[i].x<=len) continue;
        node b=make(po[i].x+len,po[i].y);      //和图中是相符的
        node a=make(po[i].x-len,po[i].y);
        lx=max(lx,a.x); rx=min(rx,b.x);
        ly=max(ly,a.y); ry=min(ry,b.y);
        if (lx>rx||ly>ry) return ;
    }
    return ;
}

void erfen()
{
    int L=; 
    int R=n;
    int ans=INF;
    while (L<=R)
    {
        int mid=(L+R)/;
        if (pd(mid)) ans=min(ans,mid),R=mid-;
        else L=mid+;
    }
    printf("%d",ans);
}

int main()
{
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);

    scanf("%d%d",&n,&m);
    for (int i=;i<=m;i++)
        scanf("%d%d",&po[i].x,&po[i].y);                
    erfen();
    return ;
}