/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 2ms 332.0 KiB
#3 Accepted 1ms 540.0 KiB
#4 Accepted 1ms 528.0 KiB
#5 Accepted 1ms 540.0 KiB
#6 Accepted 2ms 540.0 KiB
#7 Accepted 1ms 768.0 KiB
#8 Accepted 1ms 540.0 KiB
#9 Accepted 1ms 540.0 KiB
#10 Accepted 2ms 508.0 KiB
#11 Accepted 1ms 328.0 KiB
#12 Wrong Answer 2ms 540.0 KiB
#13 Accepted 1ms 540.0 KiB
#14 Wrong Answer 1ms 788.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;

typedef int64_t ll;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) 42
#endif

const double inf = 1e100;
const double eps = 1e-19;
const double PI = acos((double)-1.0);
ll sign(double x) { return (x > eps) - (x < -eps); }
struct PT {
    double x, y;
    PT() { x = 0, y = 0; }
    PT(double x, double y) : x(x), y(y) {}
    PT(const PT &p) : x(p.x), y(p.y) {}
    PT operator+(const PT &a) const { return PT(x + a.x, y + a.y); }
    PT operator-(const PT &a) const { return PT(x - a.x, y - a.y); }
    PT operator*(const double a) const { return PT(x * a, y * a); }
    friend PT operator*(const double &a, const PT &b) { return PT(a * b.x, a * b.y); }
    PT operator/(const double a) const { return PT(x / a, y / a); }
    bool operator==(PT a) const { return sign(a.x - x) == 0 && sign(a.y - y) == 0; }
    bool operator!=(PT a) const { return !(*this == a); }
    bool operator<(PT a) const { return sign(a.x - x) == 0 ? y < a.y : x < a.x; }
    bool operator>(PT 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; }
    PT perp() { return PT(-y, x); }
    double arg() { return atan2(y, x); }
    PT truncate(double r) { // returns a vector with norm r and having same direction
        double k = norm();
        if (!sign(k))
            return *this;
        r /= k;
        return PT(x * r, y * r);
    }
};
inline double cross(PT a, PT b) { return a.x * b.y - a.y * b.x; }
inline ll orientation(PT a, PT b, PT c) { return sign(cross(b - a, c - a)); }

// -1 if strictly inside, 0 if on the polygon, 1 if strictly outside
// it must be strictly convex, otherwise make it strictly convex first
ll is_point_in_convex(vector<PT> &p, const PT &x) { // O(log n)
    ll n = p.size();
    assert(n >= 3);
    ll a = orientation(p[0], p[1], x), b = orientation(p[0], p[n - 1], x);
    if (a < 0 || b > 0)
        return 1;
    ll l = 1, r = n - 1;
    while (l + 1 < r) {
        ll mid = l + r >> 1;
        if (orientation(p[0], p[mid], x) >= 0)
            l = mid;
        else
            r = mid;
    }
    ll k = orientation(p[l], p[r], x);
    if (k <= 0)
        return -k;
    if (l == 1 && a == 0)
        return 0;
    if (r == n - 1 && b == 0)
        return 0;
    return -1;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    vector<PT> points;
    for (ll i = 1; i <= n; i++) {
        double x, y;
        cin >> x >> y;
        points.push_back(PT(x, y));
    }
    // points.push_back(points.front());
    double x, y;
    cin >> x >> y;
    if (is_point_in_convex(points, PT(x, y)) == -1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

Information

Submit By
Type
Submission
Problem
P1145 Nobita's Love for Shizuka
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-12 14:15:27
Judged At
2024-12-12 14:15:27
Judged By
Score
44
Total Time
2ms
Peak Memory
788.0 KiB