fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <bits/extc++.h> /** keep-include */
  4. using namespace __gnu_pbds;
  5. #define int long long
  6.  
  7. #define rep(i, a, b) for(int i = a; i < (b); ++i)
  8. #define all(x) begin(x), end(x)
  9. #define sz(x) (int)(x).size()
  10. typedef long long ll;
  11. typedef long double ld;
  12. typedef pair<int, int> pii;
  13. typedef vector<int> vi;
  14. const ld eps = 1e-28;
  15.  
  16. struct Segment {
  17.     typedef Segment S;
  18.     pair<ld,ld> x, y;
  19.     explicit Segment(pair<ld, ld> ox, pair<ld, ld> oy) {
  20.         if (ox.first > oy.first) swap(ox, oy);
  21.         x = ox;
  22.         y = oy;
  23.     }
  24.  
  25.     ld evaluate(ld x_value) 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 + (x_value - x.first) * slope;
  29.     }
  30.  
  31.     ld find_common_point(S s) const {
  32.         ld l = max(x.first, s.x.first);
  33.         ld r = min(y.first, s.y.first);
  34.         return l + (r-l) / 2.0;
  35.     }
  36.  
  37.     bool operator==(S s) const {
  38.         ld x_value = find_common_point(s);
  39.         return abs(evaluate(x_value)-s.evaluate(x_value)) < eps;
  40.     }
  41.  
  42.     bool operator<(S s) const {
  43.         ld x_value = find_common_point(s);
  44.         return (not ((*this) == s) and evaluate(x_value) < s.evaluate(x_value));
  45.     }
  46.  
  47.  
  48.  
  49.     friend ostream& operator<<(ostream& os, S s) {
  50.         return os << "Segment((" << s.x.first << "," << s.x.second << "),(" << s.y.first << "," << s.y.second << "))";
  51.     }
  52.  
  53. };
  54.  
  55. struct Fraction {
  56.     typedef Fraction F;
  57.     int x, y;
  58.     explicit Fraction(int xx,int yy=1) {
  59.         assert(yy!=0);
  60.         if (yy<0) xx = -xx, yy = -yy;
  61.         int d = __gcd(abs(xx), abs(yy));
  62.         xx /= d;
  63.         yy /= d;
  64.         x = xx, y = yy;
  65.     }
  66.  
  67.     Fraction operator+(Fraction o) const {
  68.         return Fraction(x*o.y + o.x*y, y*o.y);
  69.     }
  70.     Fraction operator-(Fraction o) const {
  71.         return (*this) + Fraction(-o.x, o.y);
  72.     }
  73.     Fraction operator*(Fraction o) const {
  74.         return Fraction(x*o.x, y*o.y);
  75.     }
  76.     Fraction operator/(Fraction o) const {
  77.         return Fraction(x*o.y, y*o.x);
  78.     }
  79.     bool operator<(Fraction o) const {
  80.         return x*o.y < o.x*y;
  81.     }
  82.     bool operator==(Fraction o) const {
  83.         //cout << x << ' ' << o.y << ' ' << o.x << ' ' << y << endl;
  84.         return x*o.y == o.x*y;
  85.     }
  86.  
  87.     bool operator<=(Fraction o) const {
  88.         return (*this) == o or (*this) < o;
  89.     }
  90.  
  91.     friend ostream& operator<<(ostream& os, F f) {
  92.         return os << f.x << "/" << f.y;
  93.     }
  94.  
  95. };
  96.  
  97. struct SegmentInt {
  98.     typedef SegmentInt S;
  99.     pii x, y;
  100.     explicit SegmentInt(pii ox, pii oy) {
  101.         if (tie(ox.first, ox.second) > tie(oy.first, oy.second)) swap(ox, oy);
  102.         x = ox;
  103.         y = oy;
  104.     }
  105.  
  106.     Fraction evaluate(int x_value) const {
  107.         if (x.first == y.first) return Fraction(x.second, 1);
  108.         Fraction slope = Fraction(x.second - y.second, x.first - y.first);
  109.         return Fraction(x.second) + (Fraction(x_value) - Fraction(x.first)) * slope;
  110.     }
  111.  
  112.     pii find_common_point(S s) const {
  113.         int l = max(x.first, s.x.first);
  114.         int r = min(y.first, s.y.first);
  115.         return {l, r};
  116.     }
  117.  
  118.     bool operator==(S s) const {
  119.         pii common = find_common_point(s);
  120.         Fraction ta = evaluate(common.first);
  121.         Fraction tb = evaluate(common.second);
  122.         Fraction sa = s.evaluate(common.first);
  123.         Fraction sb = s.evaluate(common.second);
  124.         return (ta==sa) and (tb == sb);
  125.     }
  126.  
  127.     bool operator<(S s) const {
  128.         pii common = find_common_point(s);
  129.         return (not ((*this) == s) and (evaluate(common.first) <= s.evaluate(common.first) and evaluate(common.second) <= s.evaluate(common.second)));
  130.     }
  131.  
  132.     friend ostream& operator<<(ostream& os, S s) {
  133.         return os << "Segment((" << s.x.first << "," << s.x.second << "),(" << s.y.first << "," << s.y.second << "))";
  134.     }
  135. };
  136.  
  137. template<class T>
  138. using Tree = tree<T, null_type, less<T>, rb_tree_tag,
  139.     tree_order_statistics_node_update>;
  140.  
  141. const int maxn = 2e5;
  142. int n, m;
  143. pii poly[maxn], points[maxn];
  144. set<pii> in_poly;
  145.  
  146. pair<ld, ld> new_poly[maxn], new_points[maxn];
  147. int result[maxn];
  148.  
  149. vector<ld> all_points;
  150. vector<Segment> add_segment[maxn], rem_segment[maxn];
  151. vector<pair<pair<ld,ld>, int> > query_points[maxn];
  152. Tree<Segment> t;
  153.  
  154. vi all_int_points;
  155. vector<SegmentInt> add_segment_int[maxn], rem_segment_int[maxn], vertical_segment[maxn];
  156. vector<pair<pii, int> > query_points_int[maxn];
  157. Tree<SegmentInt> t2;
  158.  
  159. map<int, vi> M;
  160.  
  161. int get_all_points_index(ld x) {
  162.     return distance(begin(all_points), lower_bound(all(all_points), x));
  163. }
  164.  
  165. int get_all_int_points_index(int x) {
  166.     return distance(begin(all_int_points), lower_bound(all(all_int_points), x));
  167. }
  168.  
  169. pair<ld, ld> rotate(pii p) {
  170.     return {p.first * cos(1) - p.second * sin(1), p.first * sin(1) + p.second * cos(1)};
  171. }
  172.  
  173. template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
  174. template<class T>
  175. struct Point {
  176. 	typedef Point P;
  177. 	T x, y;
  178. 	explicit Point(T x=0, T y=0) : x(x), y(y) {}
  179. 	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
  180. 	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
  181. 	P operator+(P p) const { return P(x+p.x, y+p.y); }
  182. 	P operator-(P p) const { return P(x-p.x, y-p.y); }
  183. 	P operator*(T d) const { return P(x*d, y*d); }
  184. 	P operator/(T d) const { return P(x/d, y/d); }
  185. 	T dot(P p) const { return x*p.x + y*p.y; }
  186. 	T cross(P p) const { return x*p.y - y*p.x; }
  187. 	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
  188. 	T dist2() const { return x*x + y*y; }
  189. 	double dist() const { return sqrt((double)dist2()); }
  190. 	// angle to x-axis in interval [-pi, pi]
  191. 	double angle() const { return atan2(y, x); }
  192. 	P unit() const { return *this/dist(); } // makes dist()=1
  193. 	P perp() const { return P(-y, x); } // rotates +90 degrees
  194. 	P normal() const { return perp().unit(); }
  195. 	// returns point rotated 'a' radians ccw around the origin
  196. 	P rotate(double a) const {
  197. 		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
  198. 	friend ostream& operator<<(ostream& os, P p) {
  199. 		return os << "(" << p.x << "," << p.y << ")"; }
  200. };
  201.  
  202.  
  203. template<class P> bool onSegment(P s, P e, P p) {
  204. 	return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
  205. }
  206.  
  207. template<class P>
  208. bool inPolygon(vector<P> &p, P a, bool strict = true) {
  209. 	int cnt = 0, n = sz(p);
  210. 	rep(i,0,n) {
  211. 		P q = p[(i + 1) % n];
  212. 		if (onSegment(p[i], q, a)) return !strict;
  213. 		//or: if (segDist(p[i], q, a) <= eps) return !strict;
  214. 		cnt ^= ((a.y<p[i].y) - (a.y<q.y)) * a.cross(p[i], q) > 0;
  215. 	}
  216. 	return cnt;
  217. }
  218.  
  219. typedef Point<int> P;
  220. vector<P> int_poly;
  221.  
  222.  
  223.  
  224.  
  225.  
  226. main() {
  227. 	cin.tie(0)->sync_with_stdio(0);
  228. 	cin.exceptions(cin.failbit);
  229.     cin >> n >> m;
  230.     rep(i,0,n) { 
  231.         int x, y; cin >> x >> y; poly[i] = {x,y}; in_poly.insert(poly[i]); 
  232.         all_int_points.push_back(x);    
  233.     }
  234.  
  235.     memset(result, -1, sizeof(result));
  236.     rep(i,0,m) { 
  237.         int x, y; cin >> x >> y; points[i] = {x,y}; 
  238.         if (in_poly.count(points[i])) result[i] = 1;
  239.         all_int_points.push_back(x);
  240.     }
  241.  
  242.     sort(all(all_int_points));
  243.     all_int_points.erase(unique(all(all_int_points)), end(all_int_points));
  244.  
  245.  
  246.     rep(i,0,n) {
  247.         SegmentInt seg = SegmentInt(poly[i], poly[(i+1)%n]);
  248.         if (seg.x.first != seg.y.first) {
  249.             int id = get_all_int_points_index(seg.x.first);
  250.             add_segment_int[id].push_back(seg);
  251.             id = get_all_int_points_index(seg.y.first);
  252.             rem_segment_int[id].push_back(seg);
  253.         } else {
  254.             int id = get_all_int_points_index(seg.x.first);
  255.             vertical_segment[id].push_back(seg);
  256.         }
  257.     }
  258.  
  259.     rep(i,0,m) {
  260.         if (result[i] == -1) {
  261.             int id = get_all_int_points_index(points[i].first);
  262.             query_points_int[id].push_back({points[i], i});
  263.         }
  264.     }
  265.  
  266.     rep(i,0,sz(all_int_points)) {
  267.         for (auto seg: rem_segment_int[i]) {
  268.             //cout << "erase " << seg << endl;
  269.             t2.erase(seg);
  270.         }
  271.  
  272.         for (auto p: query_points_int[i]) {
  273.             SegmentInt tmp = SegmentInt(p.first, p.first);
  274.             int x = t2.order_of_key(tmp);
  275.             auto it = t2.find_by_order(x);
  276.             if (it!=end(t2) and (*it)==tmp) {
  277.                 //cout << "online " << (*it) << ' ' << tmp << ' ' << p.first.first << ' ' << p.first.second << ' ' << (*it).evaluate(p.first.first) << ' ' << tmp.evaluate(p.first.first) << endl;
  278.                 result[p.second] = 1;
  279.                 continue;
  280.             }
  281.         }
  282.  
  283.         for (auto seg: add_segment_int[i]) {
  284.             //out << "insert " << seg << endl;
  285.             t2.insert(seg);
  286.         }
  287.     }
  288.  
  289.     rep(i,0,sz(all_int_points)) {
  290.         M.clear();
  291.         for (auto p: query_points_int[i]) M[p.first.second].push_back(p.second);
  292.         for (auto p: vertical_segment[i]) {
  293.             for (auto it=M.lower_bound(p.x.second); it!=M.end() and (*it).first <= p.y.second; ++it) {
  294.                 for (auto j: (*it).second) {
  295.                     //cout << "on vertical line " << points[j].first << " " << points[j].second << endl;
  296.                     result[j] = 1;
  297.                 }
  298.             }
  299.         }   
  300.     }
  301.  
  302.  
  303.     rep(i,0,n) {
  304.         new_poly[i] = rotate(poly[i]);
  305.         all_points.push_back(new_poly[i].first);
  306.     }
  307.  
  308.     rep(i,0,m) {
  309.         new_points[i] = rotate(points[i]);
  310.         all_points.push_back(new_points[i].first);
  311.     }
  312.  
  313.     sort(all(all_points));
  314.     all_points.erase(unique(all(all_points)), end(all_points));
  315.  
  316.     rep(i,0,n) {
  317.         Segment seg = Segment(new_poly[i], new_poly[(i+1)%n]);
  318.         int id = get_all_points_index(seg.x.first);
  319.         add_segment[id].push_back(seg);
  320.         id = get_all_points_index(seg.y.first);
  321.         rem_segment[id].push_back(seg);
  322.     }
  323.  
  324.     rep(i,0,m) {
  325.         if (result[i] == -1) {
  326.             int id = get_all_points_index(new_points[i].first);
  327.             query_points[id].push_back({new_points[i], i});
  328.         }
  329.     }
  330.  
  331.     int_poly.clear();
  332.     rep(i,0,n) int_poly.push_back(P(points[i].first, points[i].second));
  333.  
  334.  
  335.     rep(i,0,sz(all_points)) {
  336.         for (auto seg: rem_segment[i]) {
  337.             //cout << "erase " << seg << endl;
  338.             t.erase(seg);
  339.         }
  340.  
  341.         for (auto p: query_points[i]) {
  342.             Segment tmp = Segment(p.first, p.first);
  343.             int x = t.order_of_key(tmp);
  344.             auto it = t.find_by_order(x);
  345.             if (it!=end(t) and (*it)==tmp) {
  346.                 assert(false);
  347.                 continue;
  348.             }
  349.  
  350.             result[p.second] = (x%2==1);
  351.         }
  352.  
  353.         for (auto seg: add_segment[i]) {
  354.             //cout << "insert " << seg << endl;
  355.             t.insert(seg);
  356.         }
  357.     }
  358.  
  359.  
  360.  
  361.     rep(i,0,m) {
  362.         //cout << points[i].first << ' ' << points[i].second << ' ';
  363.         if (result[i]) cout << "YES";
  364.         else cout << "NO";
  365.         cout << '\n';
  366.     }
  367.  
  368.     return 0;
  369. }
Success #stdin #stdout 0.01s 46116KB
comments (?)
stdin
copy 
3 3
0 0
5 5
5 0
1 1
1 2
2 1
stdout
copy 
YES
NO
YES
https://ideone.com/fJjzIF
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!