/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 588.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 1ms 540.0 KiB
#4 Accepted 1ms 772.0 KiB
#5 Accepted 1ms 540.0 KiB
#6 Accepted 1ms 772.0 KiB
#7 Accepted 1ms 584.0 KiB
#8 Accepted 1ms 552.0 KiB
#9 Accepted 2ms 620.0 KiB
#10 Accepted 1ms 768.0 KiB
#11 Accepted 1ms 556.0 KiB
#12 Accepted 2ms 548.0 KiB
#13 Accepted 1ms 772.0 KiB
#14 Accepted 1ms 512.0 KiB
#15 Accepted 1ms 540.0 KiB
#16 Accepted 2ms 528.0 KiB
#17 Accepted 1ms 512.0 KiB
#18 Accepted 2ms 580.0 KiB
#19 Accepted 1ms 540.0 KiB
#20 Accepted 2ms 492.0 KiB
#21 Wrong Answer 2ms 356.0 KiB
#22 Accepted 2ms 540.0 KiB
#23 Accepted 1ms 588.0 KiB
#24 Accepted 1ms 772.0 KiB
#25 Accepted 1ms 540.0 KiB
#26 Accepted 1ms 540.0 KiB
#27 Accepted 1ms 544.0 KiB
#28 Accepted 1ms 560.0 KiB
#29 Accepted 2ms 488.0 KiB

Code

#include<bits/stdc++.h>
using namespace std; 
using i64 = long long;

// https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
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 (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;
}

void solve() {
    int n; cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        points[i].x = x;
        points[i].y = y;
    }
    auto Nobita = Point();
    cin >> Nobita.x >> Nobita.y;
    cout << (point_in_polygon(Nobita, points) ? "YES" : "NO") << '\n';
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    // cin >> tt;
    for(int t = 1; t <= tt; t++) {
        solve();
    }
}

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 13:58:03
Judged At
2024-12-10 13:58:03
Judged By
Score
96
Total Time
2ms
Peak Memory
772.0 KiB