思路参考了这个bloghttp://hi.baidu.com/aekdycoin/blog/item/7abf85026f0d7e85d43f7cfe.html
复杂度是O(nlgn)
#define N 100005 struct node{ double x,y; }a[100005]; double cross(node a,node b,node c){//>0,ab在ac顺时针;<0,ab在ac逆时针 return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y); } int n,m; bool chk(node b){ int i,j; if(cross(a[0],b,a[1]) <= 0)return false; if(cross(a[0],b,a[n-1]) >= 0)return false; int l = 0,r = n-1,mid; int tag = 0; while(l<=r){ mid = (l+r)>>1; if(cross(a[0],b,a[mid]) >= 0){ tag = mid; l = mid+1; } else r = mid-1; } l = tag,r = tag+1; if(cross(a[l],b,a[r]) <= 0)return false; return true; } int main(){ cin>>n; int i,j; for(i=0;i<n;i++){ cin>>a[i].x>>a[i].y; } int ans = 0; cin>>m; node b; for(i=0;i<m;i++){ cin>>b.x>>b.y; if(chk(b))ans++; } if(ans==m)cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }