自动搬运

查看原文

来自洛谷，原作者为

	FZzzz **

搬运于2025-08-24 21:59:19，当前版本为作者最后更新于2021-07-14 19:07:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

整个正经做法。

每次旋转卡壳取相隔最远的两个点，把所有点和这两个点的距离丢进小根堆里，然后把这两个点删掉，这个过程重复 $k$ 次。堆的大小固定为 $k$，最后堆顶就是答案。

这样做事对的。考虑一对没有被算过的点，在每一轮中如果它的两个端点都没有被删掉，那么它必然不大于这一轮找出来的直径，否则它肯定已经被算过了。

时间复杂度大概是 $O(nk\log n)$，好像有一些神奇做法可以优化但是我懒得写了。

代码封装少比较丑。

#include<bits/stdc++.h>
using namespace std;
inline int readint(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)&&c!='-') c=getchar();
	if(c=='-'){
		f=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return f?-x:x;
}
const int maxn=1e5+5;
int n,k,x[maxn],y[maxn];
typedef long long ll;
ll cross(int a,int b,int c){
	return 1ll*(x[c]-x[a])*(y[b]-y[a])-1ll*(x[b]-x[a])*(y[c]-y[a]);
}
ll dist(int a,int b){
	return 1ll*(x[a]-x[b])*(x[a]-x[b])+1ll*(y[a]-y[b])*(y[a]-y[b]);
}
int s[maxn*2],tp;
bool vis[maxn];
pair<int,int> calc(){
	vector<int> ord;
	for(int i=1;i<=n;i++) if(!vis[i]) ord.push_back(i);
	sort(ord.begin(),ord.end(),[](int a,int b){
		if(x[a]!=x[b]) return x[a]<x[b];
		return y[a]<y[b];
	});
	s[0]=ord[0];
	tp=1;
	for(int i=1;i<(int)ord.size();i++){
		while(s[tp-1]!=ord[0]&&1ll*(y[ord[i]]-y[s[tp-1]])*(x[ord[i]]-x[s[tp-2]])>=1ll*(y[ord[i]]-y[s[tp-2]])*(x[ord[i]]-x[s[tp-1]])) tp--;
		s[tp++]=ord[i];
	}
	for(int i=(int)ord.size()-2;i>=0;i--){
		while(s[tp-1]!=ord.back()&&1ll*(y[s[tp-1]]-y[ord[i]])*(x[s[tp-2]]-x[ord[i]])>=1ll*(y[s[tp-2]]-y[ord[i]])*(x[s[tp-1]]-x[ord[i]])) tp--;
		s[tp++]=ord[i];
	}
	tp--;
	if(tp==2) return {s[0],s[1]};
	int cur=0;
	while(cross(s[tp-1],s[0],s[(cur+1)%tp])>cross(s[tp-1],s[0],s[cur])) cur=(cur+1)%tp;
	int a=s[cur],b;
	if(dist(s[cur],s[0])>dist(s[cur],s[tp-1])) b=s[0];
	else b=s[tp-1];
	for(int i=0;i<tp-1;i++){
		while(cross(s[i],s[i+1],s[(cur+1)%tp])>cross(s[i],s[i+1],s[cur])) cur=(cur+1)%tp;
		if(dist(s[cur],s[i])>dist(a,b)){
			a=s[cur];
			b=s[i];
		}
		if(dist(s[cur],s[i+1])>dist(a,b)){
			a=s[cur];
			b=s[i+1];
		}
	}
	return {a,b};
}
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	n=readint();
	k=readint();
	for(int i=1;i<=n;i++){
		x[i]=readint();
		y[i]=readint();
	}
	priority_queue<ll,vector<ll>,greater<ll>> pq;
	for(int i=0;i<min(k,n/2);i++){
		auto res=calc();
		int a=res.first,b=res.second;
		pq.push(dist(a,b));
		if((int)pq.size()>k) pq.pop();
		vis[a]=vis[b]=1;
		for(int j=1;j<=n;j++) if(!vis[j]){
			pq.push(dist(a,j));
			if((int)pq.size()>k) pq.pop();
		}
		for(int j=1;j<=n;j++) if(!vis[j]){
			pq.push(dist(b,j));
			if((int)pq.size()>k) pq.pop();
		}
	}
	printf("%lld\n",pq.top());
	return 0;
}

另外这题 kdt 复杂度应该是错的，但是我不会卡，有没有老哥教教我啊。