关于枚举点的双指针做法
查看原帖
关于枚举点的双指针做法
547295
wjwWeiwei楼主2024/12/10 21:20

显然当你把枚举边换成枚举点时,点对距离不是单峰的。直接交有92分,在sub0的第一个点WA了。

如下hack数据就卡掉了枚举点的做法:

9
-78 97
-77 87
-69 11
-52 -100
94 45
75 68
65 74
22 98
-5 98

代码:

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=2e5+5;
const db eps=1e-8;
using ll=long long;
int n;
inline int sgn(db x){
	if(fabs(x)<=eps)return 0;
	return x>0?1:-1; 
}
struct Point{
	db x,y;
	Point operator +(const Point B){return {x+B.x,y+B.y};}
	Point operator -(const Point B){return {x-B.x,y-B.y};}
	bool operator ==(const Point B){return !sgn(x-B.x)&&!sgn(y-B.y);}
	bool operator <(const Point B){
		return sgn(x-B.x)<0||(!sgn(x-B.x)&&sgn(y-B.y)<0);
	}
}a[N],qu[N];
typedef Point Vector;
inline db Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
inline db squ(db x){return x*x;}
inline db dis(Point A,Point B){return sqrt(squ(A.x-B.x)+squ(A.y-B.y));}
inline int pdis(Point A,Point B){return squ(A.x-B.x)+squ(A.y-B.y);}
int tl;
inline void Convex(){
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		while(tl>1&&Cross(qu[tl]-qu[tl-1],a[i]-qu[tl])<=0)tl--;
		qu[++tl]=a[i];
	}
	int cur=tl;
	for(int i=n-1;i>=1;i--){
		while(tl>cur&&Cross(qu[tl]-qu[tl-1],a[i]-qu[tl])<=0)tl--;
		qu[++tl]=a[i];
	}
	if(n>1)tl--;
}
int nxt[N];
inline db len(Vector A){return sqrt(squ(A.x)+squ(A.y));}
struct Line{
	Point A;Vector B;
};
inline db PTL(Point P,Line Q){
	Vector p1=P-Q.A,p2=Q.B;
	return fabs(Cross(p1,p2))/len(p2);
}
int ans;
int pre[N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	Convex();
	for(int i=1;i<=tl;i++)nxt[i]=i%tl+1;
//	if(tl>5)assert(0);
	if(tl==2){
		cout<<pdis(qu[1],qu[2])<<"\n";
		return 0;
	}
	else{
		int cur=2;
		for(int i=1;i<=tl;i++){
			while(pdis(qu[cur],qu[i])<=pdis(qu[nxt[cur]],qu[i]))cur=nxt[cur];
			ans=max(ans,pdis(qu[i],qu[cur]));
		}
		cout<<ans;
	}
	return 0;
}

那么,是否枚举点一定不可行呢,有改进的措施吗?

2024/12/10 21:20
加载中...