/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 1ms 768.0 KiB
#4 Accepted 1ms 516.0 KiB
#5 Accepted 2ms 344.0 KiB
#6 Accepted 1ms 540.0 KiB
#7 Accepted 1ms 332.0 KiB
#8 Accepted 1ms 540.0 KiB
#9 Accepted 1ms 584.0 KiB
#10 Accepted 2ms 328.0 KiB
#11 Accepted 1ms 584.0 KiB
#12 Accepted 1ms 540.0 KiB
#13 Accepted 2ms 540.0 KiB
#14 Accepted 2ms 584.0 KiB
#15 Accepted 2ms 796.0 KiB
#16 Accepted 2ms 564.0 KiB
#17 Accepted 2ms 556.0 KiB
#18 Accepted 2ms 540.0 KiB
#19 Accepted 1ms 576.0 KiB
#20 Accepted 2ms 540.0 KiB
#21 Accepted 2ms 568.0 KiB
#22 Accepted 2ms 540.0 KiB
#23 Accepted 2ms 512.0 KiB
#24 Accepted 3ms 540.0 KiB
#25 Accepted 2ms 556.0 KiB
#26 Accepted 2ms 768.0 KiB
#27 Accepted 1ms 544.0 KiB
#28 Accepted 2ms 484.0 KiB
#29 Accepted 1ms 752.0 KiB

Code

// sublime text
// {
// "cmd": ["g++.exe","-std=c++14", "${file}", "-o", "${file_base_name}.exe", "&&" , "${file_base_name}.exe<inputf.in>outputf.in"],
// "selector":"source.cpp",
// "shell":true,
// "working_dir":"$file_path"
// }

#include<bits/stdc++.h>
using namespace std;
double eps = 1e-9;
double PI = 2*acos(0.0);
int sign(double x) { return (x > eps) - (x < -eps);}
struct P{
    double x, y;
    P() { x = 0, y = 0; }
    P(double x, double y) : x(x), y(y) {}
    P(const P &p) : x(p.x), y(p.y)  {}
    P operator + (const P &a) const { return P(x + a.x, y + a.y); }
    P operator - (const P &a) const { return P(x - a.x, y - a.y); }
    P operator * (const double a) const { return P(x * a, y * a); }
    double operator * (const P& b) const{ return x * b.y - y * b.x;}
    int orientation(const P& a, const P& b) const{
       /*
        -ve if vecA is on left
        zero if collinear
        +ve if vecA on right
       */
        return sign((a - *this)*(b - *this));
    }
    P operator / (const double a) const { return P(x / a, y / a); }
    bool operator == (P a) const { return sign(a.x - x) == 0 && sign(a.y - y) == 0; }
    bool operator != (P a) const { return !(*this == a); }
    bool operator < (P a) const { return sign(a.x - x) == 0 ? y < a.y : x < a.x; }
    bool operator > (P a) const { return sign(a.x - x) == 0 ? y > a.y : x > a.x; }
    double norm() { return sqrt(x * x + y * y); }
    double norm2() { return x * x + y * y; }
    P perp() { return P(-y, x); }
    double arg() { return atan2(y, x); }
    P truncate(double r) { // returns a vector with norm r and having same direction
        double k = norm();
        if (!sign(k)) return *this;
        r /= k;
        return P(x * r, y * r);
    }
};
istream &operator >> (istream &in, P& p) { return in>>p.x>>p.y; }
ostream &operator << (ostream &out, P& p) { return out<<p.x<<" "<<p.y; }
inline double cross(P a, P b) { return a.x * b.y - a.y * b.x; }
bool is_point_on_seg(P a, P b, P p) {
    if (fabs(cross(p - b, a - b)) < eps) {
        if (p.x < min(a.x, b.x) - eps || p.x > max(a.x, b.x) + eps) return false;
        if (p.y < min(a.y, b.y) - eps || p.y > max(a.y, b.y) + eps) return false;
        return true;
    }
    return false;
}
bool is_point_on_polygon(vector<P> &p, const P& z) {
    int n = p.size();
    for (int i = 0; i < n; i++) {
    	if (is_point_on_seg(p[i], p[(i + 1) % n], z)) return 1;
    }
    return 0;
}
// returns 1e9 if the point is on the polygon 
int winding_number(vector<P> &p, const P& z) { // O(n)
    if (is_point_on_polygon(p, z)) return 1e9;
    int n = p.size(), ans = 0;
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        bool below = p[i].y < z.y;
        if (below != (p[j].y < z.y)) {
            auto orient = z.orientation(p[j], p[i]);
            if (orient == 0) return 0;
            if (below == (orient > 0)) ans += below ? 1 : -1;
        }
    }
    return ans;
}
// -1 if strictly inside, 0 if on the polygon, 1 if strictly outside
int is_point_in_polygon(vector<P> &p, const P& z) { // O(n)
    int k = winding_number(p, z);
    return k == 1e9 ? 0 : k == 0 ? 1 : -1;
}
int main(){
   int n;
    cin>>n;
    vector<P> p(n);
    for(auto &i : p){
        cin>>i;
    }
    P z;
    cin>>z;
    int ans = winding_number(p,z);
    if(ans==-1) cout<<"YES\n";
    else    cout<<"NO\n";
}

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:14:40
Judged At
2024-12-10 10:14:40
Judged By
Score
100
Total Time
3ms
Peak Memory
796.0 KiB