分析

我们需要找到一个

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

CPP

#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;
}

题解：P5086 坐标

文章操作

分析

Code

相关推荐

评论

题解：P5086 坐标