#include #include #include #include #include #include #include using namespace std; struct pt { long x, y; }; bool operator<(pt const & lhs, pt const & rhs) { return make_pair(lhs.x, lhs.y) < make_pair(rhs.x, rhs.y); } pt operator+(pt lhs, pt const & rhs) { lhs.x += rhs.x; lhs.y += rhs.y; return lhs; } pt operator-(pt lhs, pt const & rhs) { lhs.x -= rhs.x; lhs.y -= rhs.y; return lhs; } pt ccw(pt const & p) { return pt{-p.y, p.x}; } struct line { pt b, e; bool final = false; bool above = false; line* next = nullptr; line() = default; line(pt b_, pt e_) : b(b_), e(e_) { if (b.y == e.y) { final = true; if (b.y > 0) above = true; else above = false; } if (b.y > 0 || e.y > 0) { final = true; above = true; } } }; bool down_facing(line const & l) { auto const d = l.e - l.b; auto const n = ccw(d); return n.y > 0; } bool up(line const & l) { return l.e.y > l.b.y; } bool dn(line const & l) { return l.b.y > l.e.y; } // path compression line * find(line * c) { if(c->final) return c; // if infinite loop -> ball stuk below surface! if(c->next == c) { c->final = true; c->above = false; } assert(c->next); // hack to avoid infinte loop auto temp = c->next; c->next = c; c->next = find(temp); c->final = c->next->final; c->above = c->next->above; return c->next; } int main () { int n, b; cin >> n >> b; vector points(n); for(auto & p : points) { cin >> p.x >> p.y; } // make the points go from left to right (input is ccw) const auto on_xpos = [](pt const & l, pt const & r) { return l.x < r.x; }; const auto lit = min_element(points.begin(), points.end(), on_xpos); const auto minx = lit->x; rotate(points.begin(), lit, points.end()); // remove points going from right to left auto rit = max_element(points.begin(), points.end(), on_xpos); const auto maxx = rit->x; ++rit; points.erase(rit, points.end()); // make lines vector lines; lines.reserve(points.size()-1); // to avoid resizes map lines_map; // efficient x -> line map (for y << -10^6) // auto const clog_map = [&](){ // clog << '['; // bool first = true; // for(auto p : lines_map) { // if(!first) clog << ", "; // clog << p.first << " -> " << (p.second - lines.data()); // if (p.second->final) clog << (p.second->above ? 'A' : 'B'); // first = false; // } // clog << ']' << endl; // }; double windingnumber = 0; for (int i = 1; i < points.size(); ++i) { line l(points[i-1], points[i]); windingnumber += atan2(l.e.y - l.b.y, l.e.x - l.b.x); if (!down_facing(l)) continue; lines.push_back(l); auto lp = &lines.back(); // setup some next pointers in the easy cases if(lines.size() >= 2){ auto * l2 = &lines[lines.size()-2]; if (l2->e.x == l.b.x) { // if connected, balls float to neighbour // clog << "nbh" << endl; if (dn(*lp)) lp->next = l2; if (up(*l2)) l2->next = lp; } else { // else, there was an skipped edge // clog << "skip " << windingnumber << endl; if (dn(*lp) && windingnumber > 0) lp->next = lp; if (up(*l2) && windingnumber < 0) l2->next = l2; } } // what a mess if (lines_map.empty()) { // first line lines_map[l.b.x] = lp; if (dn(*lp)) { lp->final = true; lp->above = true; } } else { // find line above/below current line auto it = lines_map.lower_bound(l.b.x); --it; auto * l2 = it->second; if (l2->e.x == lp->b.x) { // continue line lines_map[lp->b.x] = lp; } else { // line is at different height auto a = l2->b - lp->b; auto b = l2->e - lp->b; assert (a.x < 0 && b.x > 0); auto h = (b.y - a.y) / double(b.x - a.x) * (-a.x) + a.y; if (h > 0) { // new line is under old lines_map.erase(++it, lines_map.end()); lines_map[lp->b.x] = lp; if (dn(*lp)) lp->next = l2; } else { // new line is above old auto right_most = lines_map.rbegin()->second; if (right_most->e.x < lp->e.x) { lines_map[right_most->e.x] = lp; if (up(*right_most)) right_most->next = lp; } } } } windingnumber = 0; } if (up(lines.back())) { lines.back().final = true; lines.back().above = true; } auto const find_line = [&](long x) -> line * { if (x < minx || x > maxx) return nullptr; auto it = lines_map.lower_bound(x); --it; return x < it->second->e.x ? it->second : nullptr; }; auto const floats_to_top = [&](line * l) { assert(l); assert(l->next || l->final); l = find(l); assert(l->final); return l->above; }; long count = 0; for (int i = 0; i < b; ++i){ long x; cin >> x; auto l = find_line(x); if (!l) count++; else if (floats_to_top(l)) count++; } cout << (b - count) << endl; }