Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- enum {LEFT, RIGHT, BEYOND, BEHIND, BETWEEN, ORIGIN, DESTINATION};
- class Point {
- public:
- int x;
- int y;
- Point(int x, int y) : x(x), y(y) {}
- Point() {}
- Point operator+(Point& p){
- return Point(x + p.x, y + p.y);
- }
- __int64_t length()
- {
- return x*x + y*y;
- }
- Point operator-(Point &p){
- return Point(x - p.x, y - p.y);
- }
- int operator==(Point &p)
- {
- return (x == p.x) && (y == p.y);
- }
- int classify(Point& p0, Point& p1){
- Point p2 = *this;
- Point a = p1 - p0;
- Point b = p2 - p0;
- double sa = a.x * b.y - b.x * a.y;
- if (sa > 0.0)
- return LEFT;
- if (sa < 0.0)
- return RIGHT;
- if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0))
- return BEHIND;
- if (a.length() < b.length())
- return BEYOND;
- if (p0 == p2)
- return ORIGIN;
- if (p1 == p2)
- return DESTINATION;
- return BETWEEN;
- }
- };
- bool pointInTriangle(Point p, Point a, Point b, Point c)
- {
- return ((p.classify (a, b) != LEFT) &&
- (p.classify(b, c) != LEFT) &&
- (p.classify(c, a) != LEFT));
- }
- enum { INSIDE, OUTSIDE, BOUNDARY };
- enum { TOUCHING, CROSSING, INESSENTIAL };
- int edgeType (Point &a, Point &v, Point &w)
- {
- switch (a.classify(v, w)) {
- case LEFT:
- return ((v.y < a.y) && (a.y <= w.y)) ? CROSSING : INESSENTIAL;
- case RIGHT:
- return ((w.y < a.y) && (a.y <= v.y)) ? CROSSING : INESSENTIAL;
- case BETWEEN:
- case ORIGIN:
- case DESTINATION:
- return TOUCHING;
- default:
- return INESSENTIAL;
- }
- }
- int pointInPolygon(Point &a, vector<Point> &p)
- {
- int parity = 0;
- for (int i = 0; i < p.size(); i++) {
- int next = i + 1;
- if (i + 1 == p.size()) {
- next = 0;
- }
- switch (edgeType(a, p[i], p[next])) {
- case TOUCHING:
- return BOUNDARY;
- case CROSSING:
- parity = 1 - parity;
- }
- }
- return (parity ? INSIDE : OUTSIDE);
- }
- inline __int64_t sign (const Point& p1, const Point& p2, const Point& p3)
- {
- return ((__int64_t) p1.x - p3.x) * (p2.y - p3.y) - ((__int64_t) p2.x - p3.x) * (p1.y - p3.y);
- }
- int main() {
- //freopen("inside.in", "r", stdin);
- //freopen("inside.out", "w", stdout);
- int n;
- cin >> n;
- int x_q, y_q;
- cin >> x_q >> y_q;
- Point q(x_q, y_q);
- vector<Point> p(n);
- for (int i = 0; i < n; ++i) {
- int x, y;
- cin >> x >> y;
- p[i].x = x, p[i].y = y;
- }
- /*
- reverse(p.begin(), p.end());
- bool need_reverse = sign(p[n - 1], p[0], p[1]) < 0;
- if (need_reverse) {
- reverse(p.begin(), p.end());
- }
- */
- auto loc = pointInPolygon(q, p);
- if (loc == BOUNDARY) {
- cout << "YES" << endl;
- } else if (loc == INSIDE) {
- cout << "YES" << endl;
- } else if (loc == OUTSIDE) {
- cout << "NO" << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement