/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 1ms 540.0 KiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 1ms 772.0 KiB
#6 Accepted 1ms 344.0 KiB
#7 Accepted 1ms 540.0 KiB
#8 Accepted 2ms 492.0 KiB
#9 Accepted 1ms 332.0 KiB
#10 Accepted 1ms 544.0 KiB
#11 Accepted 1ms 540.0 KiB
#12 Accepted 1ms 588.0 KiB
#13 Accepted 1ms 328.0 KiB
#14 Accepted 1ms 540.0 KiB
#15 Accepted 1ms 540.0 KiB
#16 Accepted 2ms 540.0 KiB
#17 Accepted 2ms 360.0 KiB
#18 Accepted 2ms 540.0 KiB
#19 Accepted 1ms 332.0 KiB
#20 Accepted 2ms 720.0 KiB
#21 Accepted 3ms 564.0 KiB
#22 Accepted 2ms 540.0 KiB
#23 Accepted 2ms 540.0 KiB
#24 Accepted 2ms 612.0 KiB
#25 Accepted 2ms 540.0 KiB
#26 Accepted 2ms 516.0 KiB
#27 Accepted 1ms 588.0 KiB
#28 Wrong Answer 2ms 328.0 KiB
#29 Accepted 1ms 540.0 KiB

Code

// C++ program for the above approach gfg
#include <bits/stdc++.h>

using namespace std;

struct Point {
    double x, y;
};

// Function to check if a point is inside a polygon using
// the ray-casting algorithm
bool isPointInPolygon(const vector<Point>& polygon,
                      const Point& point)
{
    // Number of vertices in the polygon
    int n = polygon.size();
    // Count of intersections
    int count = 0;

    // Iterate through each edge of the polygon
    for (int i = 0; i < n; i++) {
        Point p1 = polygon[i];
        // Ensure the last point connects to the first point
        Point p2 = polygon[(i + 1) % n];

        // Check if the point's y-coordinate is within the
        // edge's y-range and if the point is to the left of
        // the edge
        if ((point.y > min(p1.y, p2.y))
                && (point.y <= max(p1.y, p2.y))
                && (point.x <= max(p1.x, p2.x))) {
            // Calculate the x-coordinate of the
            // intersection of the edge with a horizontal
            // line through the point
            double xIntersect = (point.y - p1.y)
                                * (p2.x - p1.x)
                                / (p2.y - p1.y)
                                + p1.x;
            // If the edge is vertical or the point's
            // x-coordinate is less than or equal to the
            // intersection x-coordinate, increment count
            if (point.x < xIntersect) {
                count++;
            }
        }
    }
    // If the number of intersections is odd, the point is
    // inside the polygon
    return count % 2 == 1;
}

// Driver code
int main() {
    int n; cin >> n;
    vector<Point> polygon;
    for (int i = 0; i < n; i++) {
        double x, y; cin >> x >> y;
        polygon.push_back({x, y});
    }
    Point point;
    double x, y; cin >> x >> y;
    point.x = x;
    point.y = y;
    // Check if the point is inside the polygon
    if (isPointInPolygon(polygon, point)) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1145 Nobita's Love for Shizuka
Contest
LU IUJPC : Sylhet Division 2024 Replay Contest
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-10 11:17:53
Judged At
2024-12-10 11:17:53
Judged By
Score
98
Total Time
3ms
Peak Memory
772.0 KiB