-
题解:
- 求出$A$ 和$-B$ 的$Minkowsiki$和再$O(logn)$判断一个点是否在凸包内;
- $Minkowsiki$的求法比较容易忘,要多多温习才可以;
-
1 #include<bits/stdc++.h> 2 #define ld long long 3 using namespace std; 4 const int N=100010; 5 int n,m,q; 6 struct P{ 7 ld x,y; 8 P(ld _x=0,ld _y=0):x(_x),y(_y){}; 9 bool operator <(const P&a)const{return x==a.x?y<a.y:x<a.x;} 10 P operator -(const P&a)const{return P(x-a.x,y-a.y);} 11 P operator +(const P&a)const{return P(x+a.x,y+a.y);} 12 }p1[N],p2[N],ch[N],p[N<<1],Q; 13 ld crs(P a,P b){return a.x*b.y-a.y*b.x;} 14 ld len(P a){return a.x*a.x+a.y*a.y;} 15 bool cmpQ(P a,P b){return crs(a,b)>0||(crs(a,b)==0&&len(a)<len(b));} 16 char gc(){ 17 static char*P1,*P2,s[1000000]; 18 if(P1==P2)P2=(P1=s)+fread(s,1,1000000,stdin); 19 return(P1==P2)?EOF:*P1++; 20 } 21 int rd(){ 22 int x=0,f=1;char c=gc(); 23 while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();} 24 while(c>='0'&&c<='9'){x=x*10+c-'0';c=gc();} 25 return x*f; 26 } 27 void convex(P *p,int&cnt){ 28 sort(p+1,p+cnt+1); 29 int top,tmp; 30 ch[top=1]=p[1]; 31 for(int i=2;i<=cnt;++i){ 32 while(top>1&&crs(ch[top]-ch[top-1],p[i]-ch[top])<=0)top--; 33 ch[++top]=p[i]; 34 } 35 tmp=top; 36 for(int i=cnt-1;i;--i){ 37 while(top>tmp&&crs(ch[top]-ch[top-1],p[i]-ch[top])<=0)top--; 38 ch[++top]=p[i]; 39 } 40 for(int i=1;i<=top;++i)p[i]=ch[i]; 41 cnt=--top; 42 } 43 bool check(P Q){ 44 if(crs(p[2],Q)<0||crs(p[n],Q)>0)return false; 45 int pos=lower_bound(p+2,p+n+1,Q,cmpQ)-p-1; 46 return crs(p[pos+1]-p[pos],Q-p[pos])>=0; 47 } 48 int main(){ 49 #ifndef ONLINE_JUDGE 50 freopen("war.in","r",stdin); 51 freopen("war.out","w",stdout); 52 #endif 53 n=rd();m=rd();q=rd(); 54 for(int i=1;i<=n;++i)p1[i].x=rd(),p1[i].y=rd(); 55 for(int i=1;i<=m;++i)p2[i].x=-rd(),p2[i].y=-rd(); 56 convex(p1,n),convex(p2,m); 57 int cnt=0,j=1; 58 p1[n+1]=p1[1];p2[m+1]=p2[1]; 59 for(int i=1;i<=n;++i){ 60 p[++cnt]=p1[i]+p2[j]; 61 while(j<=m&&crs(p2[j+1]-p2[j],p1[i+1]-p1[i])>=0) 62 p[++cnt]=p1[i]+p2[++j]; 63 } 64 while(j<=m)p[++cnt]=p1[1]+p2[j++]; 65 n=cnt;for(int i=2;i<=n;++i)p[i]=p[i]-p[1]; 66 for(int i=1;i<=q;++i){ 67 Q.x=rd(),Q.y=rd(); 68 printf("%d\n",check(Q-p[1])); 69 } 70 return 0; 71 }
View Code