题解：UVA10256 The Great Divide

定义对于两个点集

A,B

，其闵可夫斯基和为

A+B=\{a+b,a\in A,b\in B\}

。

我们研究两个凸包之间的闵可夫斯基和，可以发现是把凸包中的边进行了平移得到的，等价于对于两个凸包中的边进行极角排序之后放在一起。凸包本来就有单调性，所以可以直接归并这些边，复杂度是

O(|A|+|B|)

的。

具体做法就是初始点是

a_0+b_0

，然后我们把凸包中的相邻点作差分（得到了边），按照斜率把种边进行归并加入，每次都在上一个点的基础上加上一个新加入的向量（边）得到一个新的点。注意求完 Minkowski 之后最好再求一次凸包，去掉一次多余的点，比如三点共线之类的。

本题等价于对于

A

和

(-B)

求闵可夫斯基和之后，判断给

(0,0)

是否在凸包之内。

按照上文所述求出凸包之后，我们任意选择一个点作为起点对于凸包进行三角剖分。也就是通过该起点和凸包中任意两个相邻点，把凸包划分为

n-2

个三角形。然后我们只需要通过叉积判断方向，二分出给定点如果被凸包包含，会在哪个三角形之内，然后再判断是否在这个三角形之内（直接用叉积对于第三条边判定即可）。注意 corner case 就是可能出现某个点恰好处于最后一条边上，特判一下即可。

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
struct Point{
	int x,y;
	bool operator < (const Point &rhs) const { return x<rhs.x||(x==rhs.x&&y<rhs.y); }
}; typedef Point Vector; vector<Point> s,t,ps;
ll Cross (Vector v1,Vector v2){ return 1ll*v1.x*v2.y-1ll*v1.y*v2.x; }
Vector operator + (Vector v1,Vector v2){ return (Vector){v1.x+v2.x,v1.y+v2.y}; }
Vector operator - (Vector v1,Vector v2){ return (Vector){v1.x-v2.x,v1.y-v2.y}; }
int n,m,q; vector<Point> H;
vector<Point> Hull(vector<Point> S){
	int sz=S.size(); if(sz<=1) return S;
	sort(S.begin(),S.end()); int k=0,t; 
	H.clear(); H.resize(2*sz); 
	for(int i=0;i<sz;H[k++]=S[i++])
		while(k>1&&Cross(S[i]-H[k-1],H[k-1]-H[k-2])>=0) k--;
	for(int i=sz-2,t=k;i>=0;H[k++]=S[i--])
		while(k>t&&Cross(S[i]-H[k-1],H[k-1]-H[k-2])>=0) k--;
	H.resize(k-1); return H;
}
vector<Point> Minkowski(vector<Point> S,vector<Point> T){
	H.clear(); H.pb(S[0]+T[0]);
	int s1=S.size(),t1=T.size(); Point s0=S[0],t0=T[0];
	for(int i=0;i<s1-1;i++) S[i]=S[i+1]-S[i];
	for(int i=0;i<t1-1;i++) T[i]=T[i+1]-T[i];
	S[s1-1]=s0-S[s1-1]; T[t1-1]=t0-T[t1-1];
	for(int i=0,j=0;i<s1||j<t1;){
		if(i==s1) H.pb(H.back()+T[j++]);
		else if(j==t1) H.pb(H.back()+S[i++]);
		else if(Cross(S[i],T[j])>=0) H.pb(H.back()+S[i++]);
		else H.pb(H.back()+T[j++]);
	}
	return H;
}
bool chk(Point n0){
	int l=0,r=s.size()-1;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(Cross(s[mid]-s[0],n0-s[0])>=0) l=mid;
		else r=mid-1;
	}
	if(l==s.size()-1){
		if(Cross(n0-s[0],n0-s[l])==0&&s[0].x<=n0.x&&n0.x<=s[l].x&&s[0].y<=n0.y&&n0.y<=s[l].y)
			return 1;
		return 0;
	}
	if(Cross(s[l+1]-s[l],n0-s[l])>=0) return 1;
	else return 0;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	while(cin>>n>>m&&n&&m){
		s.clear(); t.clear();
		for(int i=1;i<=n;i++){
			int x,y; cin>>x>>y;
			s.pb((Point){x,y});
		}
		for(int i=1;i<=m;i++){
			int x,y; cin>>x>>y;
			t.pb((Point){-x,-y});
		}
		s=Hull(s); t=Hull(t);
		s=Minkowski(s,t); s=Hull(s);
		if(chk((Point){0,0})) cout<<"No\n";
		else cout<<"Yes\n";
	}
	return 0;
}

题解：UVA10256 The Great Divide

文章操作

相关推荐

评论

题解：UVA10256 The Great Divide