C task

#pragma optimization_level 3
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <string>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <string.h>
#include <stack>
#include <assert.h>
#include <list>
#include <time.h>
#include <memory>
#include <chrono>
using namespace std;
//
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
#define cin in
//#define cout out
#define ll long long
#define db double
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define F first
#define S second
#define ms multiset
#define pb push_back
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define PI acos(-1.0)
//#define sort(a, b) sort(a.begin(), a.end(), b())
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
ifstream in("input.txt");
ofstream out("output.txt");

struct pnt {
    int x, y;
};

int n, k;
const int MAX_N = 1000;

vector<pnt> n_pnts, k_pnts;
bool used[MAX_N];
vector<vector<pnt>> hulls;

int cw(pnt a, pnt b, pnt c) {
    ll s = (ll)(a.x - b.x) * (a.y - c.y) - (a.y - b.y) * (a.x - c.x);
    return -(s == 0 ? 0 : s / abs(s));
}

class Compare {
public:
    bool operator()(const pnt& a, const pnt& b) const {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
};

void build_hull() {
    memset(used, 0, sizeof(used));
    pnt p0 = n_pnts[0], pn = n_pnts.back();
    vector<int> upper = { 0 }, lower = {0 };

    for (int i = 1; i < n_pnts.size(); i++) {
        if (used[i]) continue;

        pnt p = n_pnts[i];

        if (i == n_pnts.size() - 1 || cw(p0, p, pn) == 1) {
            while (upper.size() >= 2 && cw(n_pnts[upper[upper.size() - 2]], n_pnts[upper.back()], p) <= 0)
                upper.pop_back();
            upper.push_back(i);
        }
        if (i == n_pnts.size() - 1 || cw(p0, p, pn) == -1){
            while (lower.size() >= 2 && cw(n_pnts[lower[lower.size() - 2]], n_pnts[lower.back()], p) >= 0)
                lower.pop_back();
            lower.push_back(i);
        }
    }

    hulls.push_back(vector<pnt>());
    for (int x : upper) {
        used[x] = 1;
        hulls.back().push_back(n_pnts[x]);
    }
    for (int i = lower.size() - 2; i > 0; i--) {
        used[lower[i]] = 1;
        hulls.back().push_back(n_pnts[lower[i]]);
    }

    int p = 0;
    for (int i = 0; i < n_pnts.size(); i++) {
        if (!used[i])
            n_pnts[p++] = n_pnts[i];
    }
    n_pnts.resize(p);
}

void build_hulls() {
    sort(n_pnts.begin(), n_pnts.end(), Compare());
    while (!n_pnts.empty())
        build_hull();
}

bool is_in_tr(pnt a, pnt b, pnt c, pnt x) {
    return cw(a, b, x) >= 0 && cw(b, c, x) >= 0 && cw(c, a, x) >= 0;
}

bool is_on_line(pnt a, pnt b, pnt x) {
    return cw(a, b, x) == 0 && x.x >= a.x && x.x <= b.x;
}

bool is_in_rect(int rect, pnt x) {
    vector<pnt>& pnts = hulls[rect];
    pnt p0 = pnts[0];

    //1st upper
    int l = -1, r = pnts.size();
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (cw(p0, pnts[m], x) >= 0) l = m;
        else r = m;
    }

    if (l == -1) return 0;

    if (l == pnts.size() - 1) {
        if (is_on_line(p0, pnts[l], x)) return 1;
    }
    else if (is_in_tr(p0, pnts[l], pnts[l + 1], x)) return 1;

    return 0;
}

int find_zone(pnt x) {

}

void input() {
    cin >> n;
    n_pnts.resize(n);
    for (pnt& x : n_pnts) cin >> x.x >> x.y;

    cin >> k;
    k_pnts.resize(k);
    for (pnt& x : k_pnts) cin >> x.x >> x.y;
}

int main() {
    fast;
    input();
    build_hulls();
}