青青草原扛把子

https://codeforces.com/gym/106565

题意

给定一个正方形的边长 \(side\) ，已知该正方形的边上若干个点的具体坐标 \((x_i,y_i)\) ，要求从中选取 \(k\) 个点，使得任意两点之间的最小曼哈顿距离尽可能大，要求这个最小曼哈顿距离的最大值。

题意转化

先考虑 \(d\) 作为最小曼哈顿距离的最大值，可以得到 \(d\leq side\)

反证法证明易得：由于至少有四个点，在边上有四个点，意味着在边上相邻的两个点之间的最短边上距离 \(\leq side\)

最短曼哈顿距离 \(\leq\) 最短边上距离

最短曼哈顿距离 \(\leq side\)

考虑对边正对着两点之间距离正好为 \(side\)

对于这种情况运用反证法

假设没有这一对点的替代方案，即两个点的左右边上距离 \(\leq side\) 都没有其他点

假设两点之间的边上距离分别为 \(d_1,d_2\) ，那么有 \(d_1+d_2 = side\times 4\)

不难看出如果 \(d_i\leq side\times 2\) ，则在 \(d_i\) 上则不会有其他点

因为 \(d_1+d_2 = side\times 4\) ，所以必有一个 \(d_i\leq side\times 2\)

即必有一边不会有其他点，又因为至少有四个点，所以另外两个点只能在一侧 \(d_i-side\times 2\) 的空隙中

又因为 \(d_i\leq side\times 3\) ，所以 \(d_i-side\times 2\leq side\)

在一个 \(\leq side\) 的空隙中，塞下两个点

这两个点之间的距离肯定 \(\leq side\)

则找到了原先那一对点的替代品，使得得到答案的那对点不会出现在对边

综上所述，结论：产生答案的那一对点一定是在同边或者邻边，且距离 \(\leq side\)

也就是说曼哈顿距离 \(=\) 边上距离

所以可以把问题拆成一条线，从 \((0,0)\) 开始逆时针一直到 \((0,1)\) ，总长度为 \(side\times 4\)

可以把这条线复制一遍，因为其实是一个环

问题就是在这个环上找 \(k\) 个点使得任意两点中最小的距离最大

思路

采用二分答案

计算在二分出来的答案 \(mid\) 下，是否可以找 \(k\) 个点使得任意两点中最小的距离超过 \(mid\)

也就是可以处理出来每个点后面最近的 \(\geq mid\) 的点

然后答案就是看起点往后跳 \(k-1\) 次之后得到的点与起点的第二个复制点的距离是否 \(\leq mid\)

往后跳 \(k-1\) 次的效果可以用ST表预处理的结果快速得到

如果上面问题的答案是肯定的，那么该距离 \(mid\) 成立，可以去找有没有更大的 \(mid\)

反之去找更小的

代码

#include<bits/stdc++.h>
#define Maxn 100000
using namespace std;
int t,L,k,n;
int s[Maxn*2+5];
struct node
{
    int x,y;
}p[Maxn+5];
int nx[21][Maxn*2+5];
auto bel(int x,int y)
{
    if(y==0) return 1;
    else if(x==L) return 2;
    else if(y==L) return 3;
    else return 4;
}
int cmp(node x,node y)
{
    auto a=bel(x.x,x.y),b=bel(y.x,y.y);
    if(a!=b) return a<b;
    else if(a==1) return x.x<y.x;
    else if(a==2) return x.y<y.y;
    else if(a==3) return y.x<x.x;
    else return y.y<x.y;
}
int nxt(int x,int step)
{
    int t=0;
    while(step)
    {
        if(step&1) x=nx[t][x];
        t++;
        step>>=1;
    }
    return x;
}
bool check(int x)
{
    for(int i=1;i<=n*2;i++)
    {
        int l=i,r=n*2,best=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(s[mid]-s[i]>=x)
            {
                best=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        nx[0][i]=(best==-1?n*2:best);
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n*2;j++)
        {
            nx[i][j]=nx[i-1][nx[i-1][j]];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i+n]-s[nxt(i,k-1)]>=x) return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>L>>k>>n;
        for(int i=1;i<=n;i++)
        {
            int x,y;
            cin>>x>>y;
            p[i]={x,y};
        }
        sort(p+1,p+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            if(p[i].y==0) s[i]=p[i].x;
            else if(p[i].x==L) s[i]=L+p[i].y;
            else if(p[i].y==L) s[i]=L*3-p[i].x;
            else s[i]=L*4-p[i].y;
            s[i+n]=s[i]+L*4;
        }
        int l=0,r=L,best=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid))
            {
                best=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        cout<<best<<endl;
    }
}