Problem Explanation

The problem essentially involves determining whether Nobita is sitting strictly inside the polygon formed by Shizuka's stops. The polygon is described by a series of coordinates, with the first and last coordinates being the same (indicating a closed polygon).

To solve this, you can use common computational geometry algorithms like the Winding Number or Ray-Casting method. However, these approaches typically include points that lie on the edges of the polygon. To meet the "strictly inside" condition, you'll need to handle edge cases explicitly.

This editorial discusses the Ray-Casting Algorithm, along with edge case handling to ensure that points on the polygon's boundary are excluded from the "inside" condition.

Author's Approach

We use the Ray-Casting Algorithm to determine whether Nobita's position lies inside the polygon. Additionally, a helper function checks if the point lies exactly on the edge of the polygon. If the point is on the edge, the answer is "NO" (as the point is not strictly inside).

Complexity

• Time Complexity: O(n), where n is the number of vertices of the polygon. Each edge of the polygon is processed once to check for intersections or boundary conditions.
• Space Complexity: O(n), required for storing the polygon vertices in a vector.

Here is the implementation:

#include <iostream>
#include <vector>
using namespace std;

struct Point {
    long long x, y;
};

// Function to check if a point is on the edge of a polygon segment
bool onEdge(Point p, Point a, Point b) {
    long long crossProduct = (b.y - a.y) * (p.x - a.x) - (b.x - a.x) * (p.y - a.y);
    if (crossProduct != 0)
        return false;
    
    long long dotProduct = (p.x - a.x) * (b.x - a.x) + (p.y - a.y) * (b.y - a.y);
    if (dotProduct < 0)
        return false;
    
    long long squaredLengthBA = (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
    return dotProduct <= squaredLengthBA;
}

// Function to determine if a point is inside the polygon using the Ray-Casting algorithm
bool isInsidePolygon(vector<Point>& polygon, Point p) {
    int n = polygon.size();
    int intersections = 0;

    for (int i = 0; i < n; i++) {
        Point a = polygon[i];
        Point b = polygon[(i + 1) % n];

        // Check if the point is on the edge of the polygon
        if (onEdge(p, a, b))
            return false; // Point is not strictly inside if it's on the edge

        // Check if a ray starting from the point intersects with the edge
        if ((p.y > a.y) != (p.y > b.y)) {
            double xIntersection = a.x + (double)(b.x - a.x) * (p.y - a.y) / (b.y - a.y);
            if (p.x < xIntersection)
                intersections++;
        }
    }

    // The point is strictly inside if there are an odd number of intersections
    return intersections % 2 == 1;
}

int main() {
    int n;
    cin >> n;

    vector<Point> polygon(n);
    for (int i = 0; i < n; i++) {
        cin >> polygon[i].x >> polygon[i].y;
    }

    Point p;
    cin >> p.x >> p.y;

    if (isInsidePolygon(polygon, p)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}