凸包闵可夫斯基和的板子题。
啥是闵可夫斯基和
简单来说就是 $A+B=\{ x+y|x\in A, y\in B \}$。
咋求闵可夫斯基和
发现闵可夫斯基和的凸包就是原图所有边极角排序后顺次连接(比如下图两个蓝色的闵可夫斯基和的凸包就是红色部分)。
本题题解
如果 $A=B+C$,那么 $A-B=C$ 即 $A+(-B)=C$,所以 $B$ 取反求一次闵可夫斯基和然后每次判断 $C$ 在不在凸包中就行了。
代码很短。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
ll r=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
return r*f;
}
const int N=1e5+50;
const double pi=acos(-1);
const double eps=1e-8;
struct Point {
ll x,y;
Point operator + (const Point &) const;
Point operator - (const Point &) const;
Point operator * (const ll &) const;
bool operator == (const Point &) const;
void operator += (const Point &) ;
void operator -= (const Point &) ;
};
Point Point::operator +(const Point &a) const{
Point b={x+a.x,y+a.y};
return b;
}
Point Point::operator -(const Point &a) const{
Point b={x-a.x,y-a.y};
return b;
}
Point Point::operator *(const ll &a) const{
Point b={x*a,y*a};
return b;
}
bool Point::operator ==(const Point &a) const{
return fabs(x-a.x)<eps&&fabs(y-a.y)<eps;
}
void Point::operator +=(const Point &a) {
x+=a.x,y+=a.y;
}
void Point::operator -=(const Point &a) {
x-=a.x,y-=a.y;
}
ll dot(Point a,Point b) {
return a.x*b.x+a.y*b.y;
}
ll cross(Point a,Point b) {
return a.x*b.y-b.x*a.y;
}
double get_length(Point a) {
return sqrt(dot(a,a));
}
double get_angle(Point a,Point b) {
return acos(dot(a,b)/get_length(a)/get_length(b));
}
double get_polar_angle(Point a){
Point b={1,0};
double cos_a=1.*dot(a,b)/get_length(a);
double sin_a=1.*cross(b,a)/get_length(a);
if(sin_a>=0) return acos(cos_a);
else return 2.*pi-acos(cos_a);
}
bool cmp_for_polar_angle(Point a,Point b) {
return (fabs(get_polar_angle(a)-get_polar_angle(b))<eps)?get_length(a)<get_length(b):get_polar_angle(a)<get_polar_angle(b);
}
bool cmp_for_cross(Point a,Point b) {
return (cross(a,b)==0)?(get_length(a)<get_length(b)):cross(a,b)>0;
}
bool cmp_for_hull(Point a,Point b) {
return (a.y==b.y)?(a.x<b.x):(a.y<b.y);
}
bool dot_in_convex(Point p,Point a[],int tot) {
if(cross(p,a[1])>0||cross(a[tot],p)>0) return 0;
ll critical_p=lower_bound(a+1,a+tot+1,p,cmp_for_cross)-a-1;
Point A=p-a[critical_p],B=a[critical_p%tot+1]-a[critical_p];
return cross(p-a[critical_p],a[critical_p%tot+1]-a[critical_p])<=0;
}
Point st[N];
int tail;
int convex_hull(int tot,Point a[]) {
sort(a+1,a+tot+1,cmp_for_hull);
tail=0;
for(int i=1;i<=tot;++i) {
while(tail>1&&cross(st[tail]-st[tail-1],a[i]-st[tail-1])<=0) tail--;
st[++tail]=a[i];
}
int tmp=tail;
for(int i=tot-1;i;--i) {
while(tail>tmp&&cross(st[tail]-st[tail-1],a[i]-st[tail-1])<=0) tail--;
st[++tail]=a[i];
}
if(tot>1) tail--;
return tail;
}
Point edge_for_msch[N];
Point ans[N];
int cnt_of_msch;
Point start_p;
int minkowski_sum_of_convex_hull(int tota,Point a[],int totb,Point b[]) {
cnt_of_msch=0;
int tmpa=convex_hull(tota,a);
start_p=st[1];
for(int i=1;i<=tmpa;++i) edge_for_msch[++cnt_of_msch]=st[i%tmpa+1]-st[i];
int tmpb=convex_hull(totb,b);
start_p+=st[1];
for(int i=1;i<=tmpb;++i) edge_for_msch[++cnt_of_msch]=st[i%tmpb+1]-st[i];
sort(edge_for_msch+1,edge_for_msch+cnt_of_msch+1,cmp_for_polar_angle);
ans[1]=start_p;
for(int i=1;i<cnt_of_msch;++i) ans[i+1]=ans[i]+edge_for_msch[i];
int tmpans=convex_hull(cnt_of_msch,ans);
return tmpans;
}
int n,m,q;
Point a[N],b[N],query;
int main() {
n=(int)read(),m=(int)read(),q=(int)read();
for(int i=1;i<=n;++i) a[i].x=read(),a[i].y=read();
for(int i=1;i<=m;++i) b[i].x=read(),b[i].y=read(),b[i].x=-b[i].x,b[i].y=-b[i].y;
int tot_ans=minkowski_sum_of_convex_hull(n,a,m,b);
Point tmp=st[1];
for(int i=1;i<=tot_ans;++i) st[i]-=tmp;
while(q--) {
query.x=read(),query.y=read();
query-=tmp;
printf("%d\n",dot_in_convex(query,st,tot_ans));
}
return 0;
}
膜拜Foraino老师 st rz
膜拜F老师,F老师太强啦!