Saint John Festival UVA

给出n个点。再给出q个询问。问是否在之前n个点组成的凸包内（不包括边上）

算是存一个log查询是否在凸包内的模板吧。具体就是利用了叉积二分，叉积可以表示线段位置关系所以就可以。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long pType;
int n, top;
struct Point {
    pType x, y;
    Point(){x=y=0;}
    Point(pType _x, pType _y):x(_x),y(_y){}
    Point operator-(const Point& _p) const{return Point(x-_p.x, y-_p.y);}

    pType operator^(const Point& _p) const{return x*_p.y - y*_p.x;}

    void input(){scanf("%lld%lld", &x, &y);}
    /*sort*/
    bool operator==(const Point& _p) const{return x==_p.x&&y==_p.y;}
    bool operator<(const Point& _p) const{return x==_p.x ? y<_p.y : x<_p.x;}

} A[N], B[N], C[N];

pType cro(Point a, Point b, Point c) {return (b-a) ^ (c-a);}

void getconvex(int flag) { /*0代表不严格1代表严格*/
    sort(A, A + n);
    n = flag ? unique(A, A + n) - A : n;
    top = 0;
    for (int i = 0; i < n; ++ i) {
        while (top > 1 && cro(B[top-2], B[top-1], A[i]) < flag) -- top;
        B[top++] = A[i];
    }
    int temp = top;
    for (int i = n - 2; i >= 0; -- i) {
        while (top > temp && cro(B[top-2], B[top-1], A[i]) < flag) -- top;
        B[top++] = A[i];
    }
    if (n > 1) top--;
}

//判断点在凸包内模板 O（logn）
bool check(Point p) {
    int L = 1, R = top-1 -1;
    while (L <= R) {
        int mid = L + R >> 1;
        if (cro(B[0], B[mid], p) < 0)
            R = mid - 1;
        else {
            if(cro(B[0], B[mid+1], p) <= 0 && cro(B[mid], B[mid+1], p) >= 0)
                return 1;
            L = mid + 1;
        }
    }
    return 0;
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    while (~scanf("%lld", &n) && n) {
        for (int i = 0; i < n; ++ i) {
            A[i].input();
        }
        getconvex(1);
        long long q, cnt = 0; scanf("%lld", &q);
        for (int i = 0; i < q; ++ i) {
            Point temp;
            temp.input();
            if (check(temp)) cnt++;
        }
        printf("%lld
", cnt);

    }
    return 0;
}
/*
8
3 4
2 8
5 4
1 8
4 7
3 10
11 2
7 3
6
5 12
3 7
3 3
4 5
0 4
2 6
*/