#include #include #include #include #include #include #include #include #include #include using namespace std; using P = struct{ long long x,y; }; bool operator<(const P& l, const P& r){ return tie(l.x,l.y) < tie(r.x,r.y); } long long det(const P& a, const P& b){ return a.x*b.y - a.y*b.x; } long long det(const P& a, const P& b, const P& c){ return det(a,b) + det(b,c) + det(c,a); } using S = array; bool operator<(const S& l, const S& r){ if(l[1].x < r[0].x || l[0].x > r[1].x || l[0].x == r[0].x) return false; if(l[1].x == r[0].x) return l[0].y < l[1].y && r[0].y <= r[1].y; if(l[0].x == r[1].x) return l[1].y < l[0].y && r[1].y <= r[0].y; if(l[0].x > r[0].x) // calculate r at l[0].x and compare to l[0].y return l[0].y*(r[1].x - r[0].x) < ((l[0].x - r[0].x)*r[0].y + (r[1].x - l[0].x)*r[1].y); else // calculate l at r[0].x and compare to r[0].y return r[0].y*(l[1].x - l[0].x) > ((r[0].x - l[0].x)*l[0].y + (l[1].x - r[0].x)*l[1].y); } void dfs(int u, const vector& edges, const set& bad, vector& done, map& bs){ if(done[u]) return; done[u] = true; const auto& e = edges[u]; for(int v = 0; v < edges.size(); ++v) if(edges[v] < e) dfs(v, edges, bad, done, bs); int count = 0; auto it = bs.lower_bound(e[0].x); while(it->first <= e[1].x){ count += it->second; it = bs.erase(it); } if(e[0].y == e[1].y) return; if(e[0].y < e[1].y && bad.count(e[1].x) == 0) bs[e[1].x] += count; if(e[0].y > e[1].y && bad.count(e[0].x) == 0) bs[e[0].x] += count; } int main(){ int n, b; cin >> n >> b; vector

ps(n); // CCW order for(auto&p:ps) cin >> p.x >> p.y; auto pi = min_element(ps.begin(), ps.end()); // lowest leftmost point auto p_end = max_element(ps.begin(), ps.end()); // highest rightmost point int ans = 0; map bs; for(int i = 0; i < b; ++i){ int x; cin >> x; ++bs[x]; } bs[1e9] = 0; // Collect all left to right edges on the lower part of the polygon. vector edges; set bad; while(pi != p_end){ auto pj = next(pi); if(pj == ps.end()) pj = ps.begin(); if(pi->x < pj->x && pi->y <= 0 && pj->y <= 0){ edges.push_back({*pi, *pj}); // Check for bad endpoint. if(pi->y > pj->y){ auto pp = pi == ps.begin() ? prev(ps.end()) : prev(pi); if(pp->y < pi->y && det(*pj, *pi, *pp) > 0) bad.insert(pi->x); } if(pi->y < pj->y){ auto pp = pj == prev(ps.end()) ? ps.begin() : next(pj); if(pp->y < pj->y && det(*pj, *pi, *pp) > 0) bad.insert(pj->x); } } pi = pj; } vector done(edges.size(), false); for(int i = 0; i < edges.size(); ++i) dfs(i, edges, bad, done, bs); cout << b-accumulate(bs.begin(), bs.end(), 0, [](int s, const pair& x){return s+x.second;}) << endl; }