题解:
求出 $A$ 和 $-B$ 的 $Minkowsiki$ 和再 $O(logn)$ 判断一个点是否在凸包内;
$Minkowsiki$ 的求法比较容易忘, 要多多温习才可以;
- #include<bits/stdc++.h>
- #define ld long long
- using namespace std;
- const int N=100010;
- int n,m,q;
- struct P{
- ld x,y;
- P(ld _x=0,ld _y=0):x(_x),y(_y){};
- bool operator <(const P&a)const{return x==a.x?y<a.y:x<a.x;}
- P operator -(const P&a)const{return P(x-a.x,y-a.y);}
- P operator +(const P&a)const{return P(x+a.x,y+a.y);}
- }p1[N],p2[N],ch[N],p[N<<1],Q;
- ld crs(P a,P b){return a.x*b.y-a.y*b.x;}
- ld len(P a){return a.x*a.x+a.y*a.y;}
- bool cmpQ(P a,P b){return crs(a,b)>0||(crs(a,b)==0&&len(a)<len(b));}
- char gc(){
- static char*P1,*P2,s[1000000];
- if(P1==P2)P2=(P1=s)+fread(s,1,1000000,stdin);
- return(P1==P2)?EOF:*P1++;
- }
- int rd(){
- int x=0,f=1;char c=gc();
- while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}
- while(c>='0'&&c<='9'){x=x*10+c-'0';c=gc();}
- return x*f;
- }
- void convex(P *p,int&cnt){
- sort(p+1,p+cnt+1);
- int top,tmp;
- ch[top=1]=p[1];
- for(int i=2;i<=cnt;++i){
- while(top>1&&crs(ch[top]-ch[top-1],p[i]-ch[top])<=0)top--;
- ch[++top]=p[i];
- }
- tmp=top;
- for(int i=cnt-1;i;--i){
- while(top>tmp&&crs(ch[top]-ch[top-1],p[i]-ch[top])<=0)top--;
- ch[++top]=p[i];
- }
- for(int i=1;i<=top;++i)p[i]=ch[i];
- cnt=--top;
- }
- bool check(P Q){
- if(crs(p[2],Q)<0||crs(p[n],Q)>0)return false;
- int pos=lower_bound(p+2,p+n+1,Q,cmpQ)-p-1;
- return crs(p[pos+1]-p[pos],Q-p[pos])>=0;
- }
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("war.in","r",stdin);
- freopen("war.out","w",stdout);
- #endif
- n=rd();m=rd();q=rd();
- for(int i=1;i<=n;++i)p1[i].x=rd(),p1[i].y=rd();
- for(int i=1;i<=m;++i)p2[i].x=-rd(),p2[i].y=-rd();
- convex(p1,n),convex(p2,m);
- int cnt=0,j=1;
- p1[n+1]=p1[1];p2[m+1]=p2[1];
- for(int i=1;i<=n;++i){
- p[++cnt]=p1[i]+p2[j];
- while(j<=m&&crs(p2[j+1]-p2[j],p1[i+1]-p1[i])>=0)
- p[++cnt]=p1[i]+p2[++j];
- }
- while(j<=m)p[++cnt]=p1[1]+p2[j++];
- n=cnt;for(int i=2;i<=n;++i)p[i]=p[i]-p[1];
- for(int i=1;i<=q;++i){
- Q.x=rd(),Q.y=rd();
- printf("%d\n",check(Q-p[1]));
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2962472.html