fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <bits/extc++.h>
  3. using namespace std;
  4. using namespace __gnu_pbds;
  5.  
  6. #define rep(i,a,b) for(int i=(a); i<(b); ++i)
  7. #define all(x) begin(x), end(x)
  8. #define sz(x) (int)(x).size()
  9. using ll = long long;
  10. using ld = long double;
  11. using pii = pair<ll,ll>;
  12.  
  13. template<class T>
  14. using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  15.  
  16. const ld EPS = 1e-28L;
  17.  
  18. struct Segment {
  19.     using S = Segment;
  20.     pair<ld,ld> x, y;
  21.     explicit Segment(pair<ld, ld> ox, pair<ld, ld> oy) {
  22.         if (ox.first > oy.first) swap(ox, oy);
  23.         x = ox; y = oy;
  24.     }
  25.     ld evaluate(ld xv) const {
  26.         if (x.first == y.first) return x.second;
  27.         ld slope = (x.second - y.second) / (x.first - y.first);
  28.         return x.second + (xv - x.first) * slope;
  29.     }
  30.     ld common_x(S s) const {
  31.         ld l = max(x.first, s.x.first);
  32.         ld r = min(y.first, s.y.first);
  33.         return l + (r - l) / 2.0L;
  34.     }
  35.     bool operator==(S s) const {
  36.         ld xv = common_x(s);
  37.         return fabsl(evaluate(xv) - s.evaluate(xv)) < EPS;
  38.     }
  39.     bool operator<(S s) const {
  40.         ld xv = common_x(s);
  41.         return !((*this) == s) && evaluate(xv) < s.evaluate(xv);
  42.     }
  43. };
  44.  
  45. static inline ll mygcd(ll a, ll b) {
  46.     if (a < 0) a = -a;
  47.     if (b < 0) b = -b;
  48.     while (b) { ll t = a % b; a = b; b = t; }
  49.     return a;
  50. }
  51.  
  52. struct Fraction {
  53.     using F = Fraction;
  54.     ll x, y;
  55.     explicit Fraction(ll xx=0, ll yy=1) {
  56.         if (yy < 0) xx = -xx, yy = -yy;
  57.         ll d = mygcd(llabs(xx), llabs(yy));
  58.         x = xx / d; y = yy / d;
  59.     }
  60.     F operator+(F o) const { return F(x*o.y + o.x*y, y*o.y); }
  61.     F operator-(F o) const { return F(x*o.y - o.x*y, y*o.y); }
  62.     F operator*(F o) const { return F(x*o.x, y*o.y); }
  63.     F operator/(F o) const { return F(x*o.y, y*o.x); }
  64.     bool operator<(F o) const { return x*o.y < o.x*y; }
  65.     bool operator==(F o) const { return x*o.y == o.x*y; }
  66.     bool operator<=(F o) const { return (*this) == o || (*this) < o; }
  67. };
  68.  
  69. struct SegmentInt {
  70.     using S = SegmentInt;
  71.     pii x, y;
  72.     explicit SegmentInt(pii ox, pii oy) {
  73.         if (tie(ox.first, ox.second) > tie(oy.first, oy.second)) swap(ox, oy);
  74.         x = ox; y = oy;
  75.     }
  76.     Fraction evaluate(ll xv) const {
  77.         if (x.first == y.first) return Fraction(x.second, 1);
  78.         Fraction slope = Fraction(x.second - y.second, x.first - y.first);
  79.         return Fraction(x.second) + (Fraction(xv) - Fraction(x.first)) * slope;
  80.     }
  81.     pair<ll,ll> common_x_range(S s) const {
  82.         ll l = max(x.first, s.x.first);
  83.         ll r = min(y.first, s.y.first);
  84.         return {l, r};
  85.     }
  86.     bool operator==(S s) const {
  87.         pair<ll,ll> cr = common_x_range(s);
  88.         ll l = cr.first, r = cr.second;
  89.         Fraction ta = evaluate(l), tb = evaluate(r);
  90.         Fraction sa = s.evaluate(l), sb = s.evaluate(r);
  91.         return (ta == sa) && (tb == sb);
  92.     }
  93.     bool operator<(S s) const {
  94.         pair<ll,ll> cr = common_x_range(s);
  95.         ll l = cr.first, r = cr.second;
  96.         return !((*this) == s) && (evaluate(l) <= s.evaluate(l) && evaluate(r) <= s.evaluate(r));
  97.     }
  98. };
  99.  
  100. static inline int lower_idx_ld(const vector<ld>& v, ld x) {
  101.     return int(lower_bound(all(v), x) - v.begin());
  102. }
  103. static inline int lower_idx_ll(const vector<ll>& v, ll x) {
  104.     return int(lower_bound(all(v), x) - v.begin());
  105. }
  106. static inline pair<ld,ld> rotate_point(pii p) {
  107.     static const ld c = cosl(1.0L), s = sinl(1.0L);
  108.     return {p.first * c - p.second * s, p.first * s + p.second * c};
  109. }
  110.  
  111. int main() {
  112.     ios::sync_with_stdio(false);
  113.     cin.tie(nullptr);
  114.  
  115.     int n, m;
  116.     if (!(cin >> n >> m)) return 0;
  117.  
  118.     vector<pii> poly(n), points(m);
  119.     set<pii> on_vertex;
  120.     vector<ll> xs_int; xs_int.reserve(n + m);
  121.     rep(i,0,n) {
  122.         ll x, y; cin >> x >> y;
  123.         poly[i] = {x, y};
  124.         on_vertex.insert(poly[i]);
  125.         xs_int.push_back(x);
  126.     }
  127.     vector<int> result(m, -1);
  128.     rep(i,0,m) {
  129.         ll x, y; cin >> x >> y;
  130.         points[i] = {x, y};
  131.         if (on_vertex.count(points[i])) result[i] = 1;
  132.         xs_int.push_back(x);
  133.     }
  134.     sort(all(xs_int));
  135.     xs_int.erase(unique(all(xs_int)), xs_int.end());
  136.  
  137.     vector<vector<SegmentInt>> add_int(sz(xs_int)), rem_int(sz(xs_int)), vertical_int(sz(xs_int));
  138.     vector<vector<pair<pii,int>>> queries_int(sz(xs_int));
  139.  
  140.     rep(i,0,n) {
  141.         SegmentInt seg(poly[i], poly[(i+1)%n]);
  142.         if (seg.x.first != seg.y.first) {
  143.             int a = lower_idx_ll(xs_int, seg.x.first);
  144.             int b = lower_idx_ll(xs_int, seg.y.first);
  145.             add_int[a].push_back(seg);
  146.             rem_int[b].push_back(seg);
  147.         } else {
  148.             int id = lower_idx_ll(xs_int, seg.x.first);
  149.             vertical_int[id].push_back(seg);
  150.         }
  151.     }
  152.     rep(i,0,m) if (result[i] == -1) {
  153.         int id = lower_idx_ll(xs_int, points[i].first);
  154.         queries_int[id].push_back({points[i], i});
  155.     }
  156.  
  157.     Tree<SegmentInt> active_int;
  158.     rep(i,0,sz(xs_int)) {
  159.         for (auto& seg : rem_int[i]) active_int.erase(seg);
  160.         for (auto& qp : queries_int[i]) {
  161.             SegmentInt tmp(qp.first, qp.first);
  162.             int k = active_int.order_of_key(tmp);
  163.             auto it = active_int.find_by_order(k);
  164.             if (it != active_int.end() && (*it) == tmp) result[qp.second] = 1;
  165.         }
  166.         for (auto& seg : add_int[i]) active_int.insert(seg);
  167.     }
  168.  
  169.     rep(i,0,sz(xs_int)) {
  170.         map<ll, vector<int>> buckets;
  171.         for (auto& qp : queries_int[i]) buckets[qp.first.second].push_back(qp.second);
  172.         for (auto& seg : vertical_int[i]) {
  173.             auto it = buckets.lower_bound(seg.x.second);
  174.             while (it != buckets.end() && it->first <= seg.y.second) {
  175.                 for (int idx : it->second) result[idx] = 1;
  176.                 ++it;
  177.             }
  178.         }
  179.     }
  180.  
  181.     vector<pair<ld,ld>> poly_r(n), pts_r(m);
  182.     vector<ld> xs; xs.reserve(n + m);
  183.     rep(i,0,n) { poly_r[i] = rotate_point(poly[i]); xs.push_back(poly_r[i].first); }
  184.     rep(i,0,m) { pts_r[i] = rotate_point(points[i]); xs.push_back(pts_r[i].first); }
  185.     sort(all(xs));
  186.     xs.erase(unique(all(xs)), xs.end());
  187.  
  188.     vector<vector<Segment>> addSeg(sz(xs)), remSeg(sz(xs));
  189.     vector<vector<pair<pair<ld,ld>,int>>> queries(sz(xs));
  190.  
  191.     rep(i,0,n) {
  192.         Segment s(poly_r[i], poly_r[(i+1)%n]);
  193.         int a = lower_idx_ld(xs, s.x.first);
  194.         int b = lower_idx_ld(xs, s.y.first);
  195.         addSeg[a].push_back(s);
  196.         remSeg[b].push_back(s);
  197.     }
  198.     rep(i,0,m) if (result[i] == -1) {
  199.         int id = lower_idx_ld(xs, pts_r[i].first);
  200.         queries[id].push_back({pts_r[i], i});
  201.     }
  202.  
  203.     Tree<Segment> active;
  204.     rep(i,0,sz(xs)) {
  205.         for (auto& s : remSeg[i]) active.erase(s);
  206.         for (auto& qp : queries[i]) {
  207.             Segment tmp(qp.first, qp.first);
  208.             int k = active.order_of_key(tmp);
  209.             result[qp.second] = (k % 2 == 1);
  210.         }
  211.         for (auto& s : addSeg[i]) active.insert(s);
  212.     }
  213.  
  214.     rep(i,0,m) cout << (result[i] ? "YES\n" : "NO\n");
  215.     return 0;
  216. }
  217.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
4 4
0 0
1 1
2 0
1 5
1 0
1 1
1 2
1 3
stdout
copy 
NO
YES
YES
YES
https://ideone.com/ig7EDS
language:
C++14 (gcc 8.3)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!