题意：给定N个点，Q次询问，问当前点知否在N个点组成的凸包内。
思路：由于是凸包，我们可以利用二分求解。
二分思路1：求得上凸包和下凸包，那么两次二分，如果点在对应上凸包的下面，对应下凸包的上面，那么在凸包内。
二分思路2：求得凸包(N)，划分为N-2个三角形，二分求得对应位置，验证是否在三角形内。
（如果不是凸包，则不能这样做。
三角形代码：
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
struct point{
ll x,y;
point(){}
point(ll xx,ll yy):x(xx),y(yy){}
};
ll dot(point w,point v){ return w.x*v.x+w.y*v.y;}
ll det(point w,point v){ return w.x*v.y-w.y*v.x;}
point operator -(point w,point v){ return point(w.x-v.x,w.y-v.y);}
point a[maxn],ch[maxn]; int ttop,top,N,Q,ans;
bool cmp(point w,point v){
if(w.x!=v.x) return w.x<v.x; return w.y<v.y;
}void convex()
{
top=;
sort(a+,a+N+,cmp);
rep(i,,N) {
while(top>&&det(ch[top]-ch[top-],a[i]-ch[top-])<=) top--;
ch[++top]=a[i];
}
ttop=top;
for(int i=N-;i>=;i--){
while(top>ttop&&det(ch[top]-ch[top-],a[i]-ch[top-])<=) top--;
ch[++top]=a[i];
}
}
bool check(point A)
{
int L=,R=top-,Mid;
while(L<=R){
Mid=(L+R)>>;
if(det(ch[Mid]-ch[],A-ch[])<) R=Mid-;
else {
if(det(ch[Mid+]-ch[],A-ch[])<=&&det(ch[Mid+]-ch[Mid],A-ch[Mid])>=)
return true;
L=Mid+;
}
}
return false;
}
int main()
{
while(~scanf("%d",&N)&&N){
rep(i,,N) scanf("%lld %lld",&a[i].x,&a[i].y);
convex(); ans=;
scanf("%d",&Q);
rep(i,,Q) {
point fcy;
scanf("%lld %lld",&fcy.x,&fcy.y);
if(check(fcy)) ans++;
}
printf("%d\n",ans);
}
return ;
}
上下凸包代码：不知道咋的，一直wa1，也有可能是思路有问题吧，日后再补。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
struct point{
ll x,y;
point(){}
point(ll xx,ll yy):x(xx),y(yy){}
};
ll dot(point w,point v){ return w.x*v.x+w.y*v.y;}
ll det(point w,point v){ return w.x*v.y-w.y*v.x;}
point operator -(point w,point v){ return point(w.x-v.x,w.y-v.y);}
point a[maxn],ch[maxn]; int ttop,top,N,Q,ans;
bool cmp(point w,point v){
if(w.x!=v.x) return w.x<v.x; return w.y<v.y;
}
void convex()
{
top=;
sort(a+,a+N+,cmp);
rep(i,,N) {
while(top>&&det(ch[top]-ch[top-],a[i]-ch[top-])<=) top--;
ch[++top]=a[i];
}
ttop=top;
for(int i=N-;i>=;i--){
while(top>ttop&&det(ch[top]-ch[top-],a[i]-ch[top-])<=) top--;
ch[++top]=a[i];
}
}
bool check1(point A)
{
int L=,R=ttop-,Mid;
while(L<=R){
Mid=(L+R)>>;
if(A.x<ch[Mid].x) R=Mid-;
else {
if(ch[Mid+].x>=A.x&&det(ch[Mid+]-ch[Mid],A-ch[Mid])>=){
return true;
}
L=Mid+;
}
}
return false;
}
bool check2(point A)
{
int L=ttop,R=top-,Mid;
while(L<=R){
Mid=(L+R)>>;
if(A.x>ch[Mid].x) R=Mid-;
else {
if(ch[Mid+].x<=A.x&&det(ch[Mid+]-ch[Mid],A-ch[Mid])>=) return true;
L=Mid+;
}
}
return false;
}
int main()
{
while(~scanf("%d",&N)&&N){
rep(i,,N) scanf("%lld %lld",&a[i].x,&a[i].y);
convex(); ans=;
scanf("%d",&Q);
rep(i,,Q) {
point fcy;
scanf("%lld %lld",&fcy.x,&fcy.y);
if(check1(fcy)&&check2(fcy)) ans++;
}
printf("%d\n",ans);
}
return ;
}