/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 2ms 540.0 KiB
#3 Accepted 1ms 520.0 KiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 1ms 540.0 KiB
#6 Accepted 2ms 388.0 KiB
#7 Accepted 1ms 356.0 KiB
#8 Accepted 1ms 540.0 KiB
#9 Accepted 1ms 332.0 KiB
#10 Accepted 1ms 540.0 KiB
#11 Accepted 1ms 540.0 KiB
#12 Accepted 2ms 544.0 KiB
#13 Accepted 1ms 768.0 KiB
#14 Accepted 2ms 560.0 KiB
#15 Accepted 1ms 540.0 KiB
#16 Wrong Answer 2ms 488.0 KiB
#17 Accepted 2ms 564.0 KiB
#18 Accepted 2ms 588.0 KiB
#19 Accepted 1ms 556.0 KiB
#20 Accepted 1ms 588.0 KiB
#21 Accepted 2ms 540.0 KiB
#22 Accepted 2ms 584.0 KiB
#23 Accepted 2ms 584.0 KiB
#24 Accepted 1ms 588.0 KiB
#25 Accepted 2ms 844.0 KiB
#26 Accepted 2ms 588.0 KiB
#27 Accepted 2ms 516.0 KiB
#28 Accepted 1ms 540.0 KiB
#29 Accepted 1ms 484.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;
 
#define inf 1013161010
#define mod 1000000007
#define mod1 998244353
#define ll long long
#define lf long double
#define sz(x) ((int)x.size())
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,a,b) for(ll i=a;i<=b;i++)
#define fr freopen("x.txt","r",stdin)
#define frc freopen("y.txt","w",stdout)
#define all(x) x.begin(),x.end()
#define set0(x) memset(x,0,sizeof(x))
#define dbg cout<<"yo "<<endl;
#define pset(n) fixed<<showpoint<<setprecision(n)
 
 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pair<int,int> >
#define vll vector<ll>
#define vpll vector<pair<ll,ll> >
#define si set<int>
#define mii map<int,int>
#define umii unordered_map<int,int>
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
 
template<class T>
using min_pq = priority_queue<T,vector<T>,greater<T>>;
 
ll toint(const string &s) { stringstream ss; ss << s; ll x; ss >> x; return x; }
string tostring ( ll number ){  stringstream ss; ss<< number; return ss.str();}
 
template <typename T>
void print1(T arr[], int n) { rep(i, n) { cout << arr[i] << " "; } cout << endl; }
 
template <typename T, size_t N, size_t M>
void print2(T (&arr)[N][M], int n, int m) { rep(i, n) { rep(j, m) { cout << arr[i][j] << " "; } cout << endl; } cout << endl; }
 
template <typename T>
void print1v(const vector<T>& vec, int n) { for (int i = 0; i < n && i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl; }
 
template <typename T>
void print2v(const vector<vector<T>>& vec, int n, int m) { for (int i = 0; i < n && i < vec.size(); i++) { for (int j = 0; j < m && j < vec[i].size(); j++) { cout << vec[i][j] << " "; } cout << endl; } cout << endl;}
 
const lf pi = 2*acos(0);
const int nn = 500006;
const lf EPS = 0.000000001;
 
ll gcd(ll a,ll b){return (b==0)? a:gcd(b,a%b); }
ll fast_pow(ll a,ll m, ll mode) { if(m==0) return 1; else if(m==1) return a; ll h=fast_pow(a,m/2,mode); if(m%2==0) return ((h*h)%mode); else return ((((h*h)%mode)*a)%mode);}
ll mmi(ll b, ll mode){return fast_pow(b, mode-2, mode);}
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
  
struct Point {
    double x, y;
};

int onLine = 0;

bool isPointInPolygon(const vector<Point>& polygon,
                      const Point& point)
{
    int n = polygon.size();
    int count = 0;

    for (int i = 0; i < n; i++) {
        Point p1 = polygon[i];
        Point p2 = polygon[(i + 1) % n];

        double cross = (p2.x-p1.x)*(point.y-p1.y) - (p2.y-p1.y)*(point.x-p1.x);
        // cout << cross << endl;
        if (cross == 0) {
          onLine = 1;
        }
        if ((point.y > min(p1.y, p2.y))
            && (point.y <= max(p1.y, p2.y))
            && (point.x <= max(p1.x, p2.x))) {
            double xIntersect = (point.y - p1.y)
                                    * (p2.x - p1.x)
                                    / (p2.y - p1.y)
                                + p1.x;
            if (p1.x == p2.x || point.x <= xIntersect) {
                count++;
            }
        }
    }
    return count % 2 == 1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    // cin >> t;

    while (t--) {
      
      ll n, m, k, ans=0;
      double x, y;
      cin >> n;
      vector<Point> poly;
      rep(i, n) {
        cin >> x >> y;
        Point p = {x, y};
        poly.pb(p);
      }
      cin >> x >> y;
      Point r = {x, y};
      bool mm = isPointInPolygon(poly, r);
      if (onLine == 1) {
        cout << "NO" << endl;
        continue;
      }
      cout << (mm ? "YES" : "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:29:45
Judged At
2024-12-10 10:29:45
Judged By
Score
96
Total Time
2ms
Peak Memory
844.0 KiB