fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) begin(x), end(x)
  4. typedef long long ll;
  5. using namespace std;
  6.  
  7. #define rep(i, a, b) for (int i = a; i < (b); ++i)
  8. #define trav(a, x) for (auto &a : x)
  9. #define sz(x) (int)(x).size()
  10. typedef long long ll;
  11. typedef pair<int, int> pii;
  12. typedef vector<int> vi;
  13.  
  14. template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
  15. template <class T> struct Point {
  16.     typedef Point P;
  17.     T x, y;
  18.     explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
  19.     bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
  20.     bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
  21.     P operator+(P p) const { return P(x + p.x, y + p.y); }
  22.     P operator-(P p) const { return P(x - p.x, y - p.y); }
  23.     P operator*(T d) const { return P(x * d, y * d); }
  24.     P operator/(T d) const { return P(x / d, y / d); }
  25.     T dot(P p) const { return x * p.x + y * p.y; }
  26.     T cross(P p) const { return x * p.y - y * p.x; }
  27.     T cross(P a, P b) const { return (a - *this).cross(b - *this); }
  28.     T dist2() const { return x * x + y * y; }
  29.     double dist() const { return sqrt((double)dist2()); }
  30.     // angle to x-axis in interval [-pi, pi]
  31.     double angle() const { return atan2(y, x); }
  32.     P unit() const { return *this / dist(); } // makes dist()=1
  33.     P perp() const { return P(-y, x); }       // rotates +90 degrees
  34.     P normal() const { return perp().unit(); }
  35.     // returns point rotated 'a' radians ccw around the origin
  36.     P rotate(double a) const { return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }
  37. };
  38.  
  39. template <class P> bool onSegment(P s, P e, P p) { return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0; }
  40.  
  41. template <class P> bool inPolygon(vector<P> &p, P a, bool strict = true) {
  42.     int cnt = 0, n = sz(p);
  43.     rep(i, 0, n) {
  44.         P np = p[(i + 1) % n];
  45.         if (onSegment(p[i], np, a))
  46.             return !strict;
  47.         // or: if (segDist(p[i], np, a) <= eps) return !strict;
  48.         cnt += ((a.y >= np.y) - (a.y >= p[i].y)) * a.cross(p[i], np) > 0;
  49.     }
  50.     return cnt & 1;
  51. }
  52.  
  53. typedef Point<ll> P;
  54.  
  55. signed main() {
  56.     ios::sync_with_stdio(0);
  57.     cin.tie(0);
  58.     int N;
  59.     while (true) {
  60.         cin >> N;
  61.         if (N == 0) {
  62.             break;
  63.         }
  64.         vector<P> poly;
  65.         for (int i = 0; i < N; i++) {
  66.             P a;
  67.             cin >> a.x >> a.y;
  68.             poly.push_back(a);
  69.         }
  70.         int M;
  71.         cin >> M;
  72.         for (int i = 0; i < M; i++) {
  73.             P a;
  74.             cin >> a.x >> a.y;
  75.             auto resa = inPolygon(poly, a, true), resb = inPolygon(poly, a, false);
  76.             if (resa != resb)
  77.                 cout << "on" << endl;
  78.             else
  79.                 cout << (resa ? "in" : "out") << endl;
  80.         }
  81.     }
  82. }
Time limit exceeded #stdin #stdout 5s 4210688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/T4D6qk
language:
C++14 (gcc 8.3)
created:
6 years 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!