/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 1ms 800.0 KiB
#4 Accepted 1ms 540.0 KiB
#5 Wrong Answer 1ms 512.0 KiB
#6 Accepted 2ms 672.0 KiB
#7 Wrong Answer 1ms 556.0 KiB

Code

#include <bits/stdc++.h>
#include <iostream>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set1;
typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set2;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_s;
typedef tree<pair<int, int>, null_type, less_equal<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_s2;
typedef long long int ll;
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
const int N = 1200300;
#define pi 2 * acos(0.0)
#define vll vector<ll>
#define pq_ priority_queue
#define pq_min <int,vector<int>,greater<int>>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pb push_back
#define sp ' '
#define sz(n) (int)n.size()
#define all(n) n.begin(), n.end()
#define rall(n) n.rbegin(), n.rend()
#define YES cout << "YES\n";
#define yes cout << "yes\n";
#define NO cout << "NO\n";
#define no cout << "no\n";
#define bye return 0;
#define ss second;
#define ff first;
const double eps = 1e-9;
const int MAX = 1e5;
const int lim = 1e6;
bool odd(ll num) { return ((num & 1) == 1); }
bool even(ll num) { return ((num & 1) == 0); }
bool isEqual(double a, double b) { return abs(a - b) < eps; }
bool isGreater(double a, double b) { return a >= b + eps; }
bool isGreaterEqual(double a, double b) { return a > b - eps; }
#define tc     \
    int tt;    \
    cin >> tt; \
    while (tt--)
#define mset(n, v) memset(n, v, sizeof(n))
#define chk(n) for (auto it : n)
#define ff1(i, n) for (int i = 1; i <= n; i++)
#define lcm(a, b) (((a) * (b)) / __gcd(a, b))
int dx[8] = {1, -1, 0, 0, 1, -1, -1, 1};
int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
ll mn(ll x, ll y)
{
    if (x < y)
        return x;
    else
        return y;
}
ll maxx(ll x, ll y)
{
    if (x > y)
        return x;
    else
        return y;
}
string bin(int n)
{
    std::string binary;

    while (n > 0)
    {
        ll x=n%2;
        char y = x+'0';
        binary+=y;
        n /= 2;
    }

    // Reverse the vector to get the binary representation in correct order
    std::reverse(binary.begin(), binary.end());

    return binary;
}


ll POW(ll a, ll b)
{
    if (!b)
        return 1;
    ll r = POW(a, b / 2);
    if (b % 2)
        return r * r * a;
    else
        return r * r;
}
void pri(vi v)
{
    for (auto it : v)
        cout << it << ' ';
    cout << endl;
}
void pri1(vi v)
{
    for (auto it : v)
        cout << it << ' ';
  
}
void pro(vll v)
{
    for (auto it : v)
        cout << it << ' ';
    cout << endl;
}
int mex(vi v, int l, int r)
{
    vi a;
    for (int i = l; i <= r; i++)
    {
        a.pb(v[i]);
    }
    sort(all(a));
    for (int i = 0, j = 1; i < a.size(); i++)
    {
        if (a[i] == j)
        {
            j++;
        }
        else
        {
            return j;
        }
    }
    return a.back() + 1;
}
vector<int> cps(const vector<int> &arr)
{
    int n = arr.size();
    vector<int> prefixSum(n);

    if (n > 0)
    {
        prefixSum[0] = arr[0];
        for (int i = 1; i < n; ++i)
        {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }
    }

    return prefixSum;
}

bool comp(pair<int, int> x, pair<int, int> y)
{
    if (x.second > y.second)
        return true;
    else if (x.second == y.second)
    {
        if (x.first > y.first)
            return true;
        else
            return false;
    }
    else
        return false;
}
bool comp1(pair<int, pair<int, int>> x, pair<int, pair<int, int>> y)
{
    if (x.first > y.first)
        return true;
    else if (x.first == y.first)
    {
        if (x.second.second < y.second.second)
            return true;
        else
            return false;
    }
    else
        return false;
}
bool comp2(pair<int, pair<int, int>> x, pair<int, pair<int, int>> y)
{
    if (x.second.first > y.second.first)
        return true;
    else if (x.second.first == y.second.first)
    {
        if (x.second.second < y.second.second)
            return true;
        else
            return false;
    }
    else
        return false;
}
ll PoW(ll base, ll exponent)
{
    ll result = 1;
    for (int i = 0; i < exponent; ++i)
    {
        result = (result * base) % 10;
        ;
    }
    return result;
}

bool isp(ll num)
{
    ll om = num;
    ll rm = 0;
    while (num > 0)
    {
        ll digit = num % 10;
        rm = rm * 10 + digit;
        num /= 10;
    }
    return om == rm;
}
string lcs(const std::vector<std::string> &strs)
{
    std::vector<std::string::const_reverse_iterator> backs;
    std::string s;
    if (strs.size() == 0)
        return "";
    if (strs.size() == 1)
        return strs[0];
    for (auto &str : strs)
        backs.push_back(str.crbegin());
    while (backs[0] != strs[0].crend())
    {
        char ch = *backs[0]++;
        for (std::size_t i = 1; i < strs.size(); i++)
        {
            if (backs[i] == strs[i].crend())
                goto done;
            if (*backs[i] != ch)
                goto done;
            backs[i]++;
        }
        s.push_back(ch);
    }
done:
    reverse(s.begin(), s.end());
    return s;
}
bool leap(int year)
{
    return (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0));
}
bool isd(string s, ll d, ll y)
{
    if (d == 32)
        return 0;
    if (s == "April" || s == "June" || s == "September" || s == "November")
    {
        if (d == 31)
            return 0;
        return 1;
    }
    if (d > 28 && s == "February")
    {
        if (d == 29 && leap(y))
        {
            return 1;
        }
        return 0;
    }
    return 1;
}
vll pref(vll v)
{
    vll pr;
    pr.pb(v.front());
    for (int i = 1; i < v.size(); i++)
    {
        pr.pb(v[i] + pr[i - 1]);
    }
    return pr;
}
ll cxor(vi v, ll l, ll r)
{
    ll xo = v[l];
    for (int i = l + 1; i <= r; i++)
    {
        xo ^= v[i];
    }
    return xo;
}
#define seea(a, x, y)           \
    for (int i = x; i < y; i++) \
    {                           \
        cin >> a[i];            \
    }
#define seev(v, n)              \
    for (int i = 0; i < n; i++) \
    {                           \
        int x;                  \
        cin >> x;               \
        v.push_back(x);         \
    }
#define sees(s, n)              \
    for (int i = 0; i < n; i++) \
    {                           \
        int x;                  \
        cin >> x;               \
        s.insert(x);            \
    }
bool is(int num, int pos)
{
    // Create a mask with only the i'th bit set
    int mask = 1 << pos;

    // Perform bitwise AND operation to isolate the i'th bit
    int result = num & mask;

    // Check if the result is non-zero (bit is set)
    return result != 0;
}

// By Nitin Patel
// Function to merge two sorted subarrays of a given array
void merge(long long start, long long end,
           vector<long long> &prefix)
{
    long long n = end - start + 1;
    long long mid = (start + end) / 2;
    vector<long long> temp(n, 0);
    long long i = start;
    long long j = mid + 1;
    long long k = 0;

    // Merge the two subarrays in sorted order
    while (i <= mid and j <= end)
    {
        if (prefix[i] <= prefix[j])
        {
            temp[k++] = prefix[i++];
        }
        else
        {
            temp[k++] = prefix[j++];
        }
    }

    // Copy the remaining elements of the left subarray, if
    // any
    while (i <= mid)
    {
        temp[k++] = prefix[i++];
    }

    // Copy the remaining elements of the right subarray, if
    // any
    while (j <= end)
    {
        temp[k++] = prefix[j++];
    }

    // Copy the merged subarray back to the original array
    for (int t = start; t <= end; t++)
    {
        prefix[t] = temp[t - start];
    }
}

bool isvo(char x)
{
    if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u')
        return 1;
    return 0;
}
bool is_prime(ll x)
{
    for (ll i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            return 0;
        }
    }
    return 1;
}
bool cm(pair<char, pair<int, int>> x, pair<char, pair<int, int>> y)
{
    if (x.second.first == y.second.first)
    {
        if (x.second.second > y.second.second)
        {
            return 1;
        }
        return 0;
    }
    else
    {
        return x.second.first < y.second.first;
    }
}

vll sieve(ll n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false; // 0 and 1 are not prime numbers.

    for (ll i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (ll j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    ll cn=0;
    vll primes;
    for (ll i = 2; i <= n; i++) {
        if (is_prime[i]) {
            if(i<=n*n)
                primes.pb(i);
          
        }
    }
    return primes;
}
bool cc(pair<vi,int> xx,pair<vi,int> yy){
   ll cn=0;;
    vi x=xx.first, y=yy.first;
    for(int i=0;i<5;i++){
        if(x[i] <y[i]){
            cn++;
        }
    }
    return cn>5-cn;

}
vi mxa(vi nums, ll k) {
    vi res;
    deque<int> dq; 

    for(int i = 0; i < nums.size(); i++){
        if(!dq.empty() && dq.front() == i - k){
            dq.pop_front();
        }
        while(!dq.empty() && nums[dq.back()] < nums[i]){
            dq.pop_back();
        }
        dq.push_back(i);
        if(i >= k - 1){
            res.push_back(nums[dq.front()]);

        }
    }

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

int main() {
    ll n;
    cin >> n;
    vector<Point> v(n);  
    ll mx = -1e9, my = 1e10;
    for (int i = 0; i < n; i++) {
        cin >> v[i].x >> v[i].y;
        mx = max(v[i].x*1ll, mx); 
        my = min(v[i].y*1ll, my); 
    }
    Point p;
    cin >> p.x >> p.y;
    Point extreme = {mx, my};  
    ll count = 0, i = 0;
    do {
        int next = (i + 1) % n;
        if (doin(v[i], v[next], p, extreme)) {
            if (orientation(v[i], p, v[next]) == 0) {
                cout << (onSegment(v[i], p, v[next]) ? "YES\n" : "NO\n");
                return 0;
            }
            count++;
        }
        i = next;
    } while (i != 0);

    if (count % 2 == 1) {
        YES;
    } else {
        NO;
    }

    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 12:46:44
Judged At
2024-12-10 12:46:44
Judged By
Score
16
Total Time
2ms
Peak Memory
800.0 KiB