题解：P5086 坐标

_std_O2 · 2025-07-07 20:56:24 · 题解

分析

我们需要找到一个 j 使得 X _ i - X _ j = Y _ i - Y _ j = Z _ i - Z _ j = Q _ i - Q _ j。

此时容易发现 X _ i - Y _ i = X _ j - Y _ j , Z _ i - Y _ i = Z _ j - Y_j , Q_i - Z_i=Q_j-Z_j。

也就是它们的增减性相同，且变化量相同，我们不妨将这种相同的增减性与变化量映射为一个值，好将它们放为一类。在这些映射值相同的坐标中，就是优美坐标了，我们此时只需枚举找到 j−i 的最小值和 i+j 的最大值就行了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,MOD=1e9+7;
int minn=1e9+7,maxn;
long long w[N],n;
struct node{
    int x,y,z,q,rank,num;
}a[N];
bool cmp(node x,node y){
    if(x.rank==y.rank) return x.num<y.num;
    return x.rank<y.rank; 
}
inline int read(){
     int w = 0  , f = 1;
    char ch = getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f = -1;
        ch = getchar();
    }
    while('0'<=ch&&ch<='9'){
        w = w*10+(ch-'0');
        ch = getchar();
    }
    return w*f;
}
map<string,int> mp;
int cnt=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        a[i].x=read(),a[i].y=read(),a[i].z=read(),a[i].q=read();
        string s=to_string(a[i].y-a[i].x)+" "+to_string(a[i].z-a[i].y)+" "+to_string(a[i].q-a[i].z);
        if(!mp[s]) mp[s]=++cnt;
        a[i].rank=mp[s],a[i].num=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        if(a[i].rank==a[i+1].rank) 
            minn=min(minn,a[i+1].num-a[i].num),
            maxn=max(maxn,a[i].num+a[i+1].num);
    cout<<minn<<" "<<maxn;
}