洛谷5086 坐标

题意

有 $n(\le 5\times 10^5)$ 个四维空间点，坐标为 $(x_i,y_i,z_i,q_i)$ 。要求点对 $(i,j)$ 满足：

$$x_i-x_j=y_i-y_j=z_i-z_j=q_i-q_j$$

求 $j-i$ 的最小值及 $i+j$ 的最大值。

题解

题意即要求两点的 $x-y,y-z,z-q$ 相等。直接拿个 map 就能水过去。

#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
#define ppi pair<pii,int>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

map <ppi,int> m;
int n,a,b,c,d;

signed main()
{
    n=read();
    int ans1=1e9,ans2=0;
    for (int i=1;i<=n;i++)
    {
        a=read(); b=read(); c=read(); d=read();
        int res=m[mp(mp(a-b,b-c),c-d)];
        if (res)
        {
            ans1=min(ans1,i-res);
            ans2=max(ans2,i+res);
        }
        m[mp(mp(a-b,b-c),c-d)]=i;
    }
    return !printf("%d %d",ans1,ans2);
}