/ 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 576.0 KiB
#4 Accepted 2ms 516.0 KiB
#5 Accepted 1ms 328.0 KiB
#6 Accepted 1ms 540.0 KiB
#7 Accepted 1ms 540.0 KiB
#8 Accepted 1ms 540.0 KiB
#9 Accepted 2ms 748.0 KiB
#10 Accepted 1ms 540.0 KiB
#11 Accepted 2ms 348.0 KiB
#12 Accepted 2ms 328.0 KiB
#13 Accepted 1ms 540.0 KiB
#14 Accepted 1ms 332.0 KiB
#15 Accepted 2ms 496.0 KiB
#16 Accepted 1ms 540.0 KiB
#17 Accepted 2ms 332.0 KiB
#18 Accepted 2ms 540.0 KiB
#19 Accepted 2ms 492.0 KiB
#20 Accepted 2ms 328.0 KiB
#21 Accepted 3ms 524.0 KiB
#22 Accepted 3ms 528.0 KiB
#23 Accepted 2ms 540.0 KiB
#24 Accepted 3ms 576.0 KiB
#25 Accepted 2ms 796.0 KiB
#26 Accepted 3ms 572.0 KiB
#27 Accepted 1ms 516.0 KiB
#28 Wrong Answer 2ms 516.0 KiB
#29 Accepted 1ms 336.0 KiB

Code

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

using namespace std;

struct Point {
    double x, y;
};

// Checking if a point is inside a polygon
bool point_in_polygon(Point point, vector<Point> polygon)
{
    int num_vertices = polygon.size();
    double x = point.x, y = point.y;
    bool inside = false;

    // Store the first point in the polygon and initialize
    // the second point
    Point p1 = polygon[0], p2;

    // Loop through each edge in the polygon
    for (int i = 1; i <= num_vertices; i++) {
        // Get the next point in the polygon
        p2 = polygon[i % num_vertices];

        // Check if the point is above the minimum y
        // coordinate of the edge
        if (y > min(p1.y, p2.y)) {
            // Check if the point is below the maximum y
            // coordinate of the edge
            if (y <= max(p1.y, p2.y)) {
                // Check if the point is to the left of the
                // maximum x coordinate of the edge
                if (x <= max(p1.x, p2.x)) {
                    // Calculate the x-intersection of the
                    // line connecting the point to the edge
                    double x_intersection
                        = (y - p1.y) * (p2.x - p1.x)
                          / (p2.y - p1.y)
                          + p1.x;

                    // Check if the point is on the same
                    // line as the edge or to the left of
                    // the x-intersection
                    if (p1.x == p2.x
                            || x <= x_intersection) {
                        // Flip the inside flag
                        inside = !inside;
                    }
                }
            }
        }

        // Store the current point as the first point for
        // the next iteration
        p1 = p2;
    }

    // Return the value of the inside flag
    return inside;
}

// 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 (point_in_polygon(point, polygon)) {
        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 10:56:52
Judged At
2024-12-10 10:56:52
Judged By
Score
98
Total Time
3ms
Peak Memory
796.0 KiB