/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Wrong Answer 1ms 600.0 KiB
#3 Wrong Answer 1ms 556.0 KiB

Code

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

struct Point{
    int x, y;
};
bool onseg(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));
}
int ori(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;
    return(val>0)?1:2;
}
bool insect(Point p1, Point q1, Point p2, Point q2){
    int o1=ori(p1, q1, p2);
    int o2=ori(p1, q1, q2);
    int o3=ori(p2, q2, p1);
    int o4=ori(p2, q2, q1);
    if(o1!=o2 && o3!=o4) return true;
    if(o1==0 && onseg(p1, p2, q1)) return true;
    if(o2==0 && onseg(p1, q2, q1)) return true;
    if(o3==0 && onseg(p2, p1, q2)) return true;
    if(o4==0 && onseg(p2, q1, q2)) return true;

    return false;
}
bool ok(vector<Point>& v, Point p){
    int n=v.size();
    if(n<3) return false;
    Point extreme={1000000000, p.y};
    int count=0, i=0;
    do{
        int next=(i+1) % n;
        if(insect(v[i], v[next], p, extreme)){
            if(ori(v[i], p, v[next])==0 &&
                onseg(v[i], p, v[next])){
                return false;
            }

            count++;
        }
        i=next;
    }while(i!=0);
    return count % 2==1;
}

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

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

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

    if(ok(v, p)){
        cout << "YES\n";
    } else{
        cout << "NO\n";
    }

    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:18:57
Judged At
2024-12-10 10:18:57
Judged By
Score
0
Total Time
1ms
Peak Memory
600.0 KiB