/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 768.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 1ms 540.0 KiB
#4 Accepted 1ms 328.0 KiB
#5 Accepted 1ms 540.0 KiB
#6 Accepted 1ms 540.0 KiB
#7 Accepted 1ms 544.0 KiB
#8 Accepted 1ms 540.0 KiB
#9 Accepted 2ms 540.0 KiB
#10 Accepted 2ms 404.0 KiB
#11 Accepted 1ms 540.0 KiB
#12 Accepted 1ms 540.0 KiB
#13 Accepted 2ms 540.0 KiB
#14 Accepted 1ms 540.0 KiB
#15 Accepted 2ms 540.0 KiB
#16 Accepted 1ms 540.0 KiB
#17 Accepted 1ms 560.0 KiB
#18 Accepted 1ms 588.0 KiB
#19 Accepted 1ms 772.0 KiB
#20 Accepted 2ms 552.0 KiB
#21 Wrong Answer 2ms 516.0 KiB
#22 Accepted 2ms 332.0 KiB
#23 Accepted 2ms 772.0 KiB
#24 Accepted 2ms 332.0 KiB
#25 Accepted 3ms 512.0 KiB
#26 Accepted 3ms 496.0 KiB
#27 Accepted 2ms 328.0 KiB
#28 Wrong Answer 2ms 332.0 KiB

Code

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

struct Point {
    int x, y;
};

// Function to check if a point lies on a line segment
bool onSegment(Point p, Point q, Point r) {
    return (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
            q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y));
}

// Function to find the orientation of an ordered triplet (p, q, r)
// 0 -> p, q and r are collinear
// 1 -> Clockwise
// 2 -> Counterclockwise
int orientation(Point p, Point q, Point r) {
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0; // Collinear
    return (val > 0) ? 1 : 2; // Clockwise or Counterclockwise
}

// Function to check if two line segments intersect
bool doIntersect(Point p1, Point q1, Point p2, Point q2) {
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // General case
    if (o1 != o2 && o3 != o4) return true;

    // Special cases
    // p1, q1 and p2 are collinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

    // p1, q1 and q2 are collinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

    // p2, q2 and p1 are collinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

    // p2, q2 and q1 are collinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // Doesn't fall in any of the above cases
}

// Function to check if a point is inside a polygon
bool isInside(vector<Point>& polygon, int n, Point p) {
    // There must be at least 3 vertices in the polygon
    if (n < 3) return false;

    // Create a point for the ray
    Point extreme = {10000, p.y};

    // Count intersections of the ray with polygon edges
    int count = 0, i = 0;
    do {
        int next = (i + 1) % n;

        // Check if the line segment from polygon[i] to polygon[next]
        // intersects with the ray from p to extreme
        if (doIntersect(polygon[i], polygon[next], p, extreme)) {
            // If the point is collinear with a polygon edge, check if it lies on the segment
            if (orientation(polygon[i], p, polygon[next]) == 0) {
                return onSegment(polygon[i], p, polygon[next]);
            }

            count++;
        }
        i = next;
    } while (i != 0);

    // Return true if count is odd, false otherwise
    return count % 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 novita;
    cin >> novita.x >> novita.y;

    if (isInside(polygon, n, novita)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1145 Nobita's Love for Shizuka
Contest
LU Divisonal Contest Problem Testing Round
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-06 14:59:31
Judged At
2024-12-06 14:59:31
Judged By
Score
92
Total Time
3ms
Peak Memory
772.0 KiB