QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187720#6403. Master of PolygonUESTC_Guest_WiFiWA 60ms3612kbC++1711.3kb2023-09-24 21:16:572023-09-24 21:16:57

Judging History

你现在查看的是最新测评结果

  • [2023-09-24 21:16:57]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:3612kb
  • [2023-09-24 21:16:57]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size) memset(array, value, ((size) + 5) * sizeof(decltype(array[0])))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v) (sort(vecall(v), greater<decltype(v.back())>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
#define vecunique(v) ((v).resize(unique(vecall(v)) - (v).begin()))
using namespace std;
using db = long long;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;

const db PI = acos(-1.0L);

const db eps = 1e-8;

int dcmp(const db x)
{
    if (abs(x) <= eps)
        return 0;
    return x < 0 ? -1 : 1;
}

struct Point
{
    db x, y;

    Point() = default;

    Point(db x, db y) : x(x), y(y) {}

    bool operator==(const Point &a) const
    {
        return (abs(x - a.x) <= eps && abs(y - a.y) <= eps);
    }

    Point operator+(const Point &a) const { return Point(x + a.x, y + a.y); }

    Point operator-(const Point &a) const { return Point(x - a.x, y - a.y); }

    Point operator-() const { return Point(-x, -y); }

    Point operator*(const db &k) const { return Point(k * x, k * y); }

    Point operator/(const db &k) const { return Point(x / k, y / k); }

    db operator*(const Point &a) const { return x * a.x + y * a.y; } // Dot
    db operator^(const Point &a) const { return x * a.y - y * a.x; } // Cross
    bool operator<(const Point &a) const
    {
        if (abs(x - a.x) <= eps)
            return y < a.y - eps;
        return x < a.x - eps;
    }

    bool is_par(const Point &a) const { return abs((*this) ^ a) <= eps; }

    bool is_ver(const Point &a) const { return abs((*this) * a) <= eps; }

    int toleft(const Point &a) const
    {
        auto t = (*this) ^ a;
        return (t > eps) - (t < -eps);
    }

    db len() const { return sqrt((*this) * (*this)); }

    db dis(const Point &a) const { return (a - (*this)).len(); }

    db ang(const Point &a) const
    {
        return acos(((*this) * a) / (this->len() * a.len()));
    }

    Point rot(const db &rad) const
    {
        return Point(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
    }

    Point rot(const db &cosr, const db &sinr) const
    {
        return {x * cosr - y * sinr, x * sinr + y * cosr};
    } // 逆时针旋转(给定角度的正弦与余弦)
};

using vp = vector<Point>;

bool argcmp(const Point &a, const Point &b)
{
    int ha = 0, hb = 0;
    if (a.y < -eps || (abs(a.y) <= eps && a.x >= -eps))
        ha = -1;
    else
        ha = 1;
    if (b.y < -eps || (abs(b.y) <= eps && b.x >= -eps))
        hb = -1;
    else
        hb = 1;
    if (ha != hb)
        return ha < hb;
    auto t = (a == Point(0, 0) ? Point(1, 0) : a) ^ (b == Point(0, 0) ? Point(1, 0) : b);
    if (abs(t) <= eps)
        return a * a < b * b - eps;
    return t > eps;
}

struct Line
{
    Point p, v; // p+tv
    Line() = default;

    Line(Point p, Point v) : p(p), v(v) {}

    bool operator==(const Line &a) const { return (v.is_par(a.v) && v.is_par(p - a.p)); }

    bool is_par(const Line &a) const { return (v.is_par(a.v) && !v.is_par(p - a.p)); }

    bool is_ver(const Line &a) const { return v.is_ver(a.v); }

    bool is_on(const Point &a) const { return v.is_par(a - p); }

    int toleft(const Point &a) const { return v.toleft(a - p); }

    Point inter(const Line &a) const { return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v)); }

    db dis(const Point &a) const { return abs(v ^ (a - p)) / v.len(); }

    Point proj(const Point &a) const { return p + v * ((v * (a - p)) / (v * v)); }

    bool operator<(const Line &a) const
    {
        if (abs(v ^ a.v) <= eps && v * a.v >= -eps)
            return ((a.p - p) ^ v) > eps;
        return argcmp(v, a.v);
    }
};

using vl = vector<Line>;

struct Segment
{
    Point a, b;

    Segment() = default;

    Segment(Point a, Point b) : a(a), b(b) {}

    bool is_on(const Point &c) const
    {
        return c == a || c == b || ((c - a) * (b - c) >= -eps && dcmp((c-a)^(c-b))==0);
    }

    Point inter(const Segment &c) const { return Line(a, b - a).inter(Line(c.a, c.b - c.a)); }

    bool is_cross(const Segment &c)
    {
        Point p = inter(c);
        return (p - a) * (b - p) >= -eps && (p - c.a) * (c.b - p) >= -eps;
    }
};

struct Polygon
{
    vector<Point> p;

    Polygon() = default;

    Polygon(vp p) : p(std::move(p)) {}

    inline size_t nxt(const size_t &i) const { return i == p.size() - 1 ? 0 : i + 1; }

    inline size_t pre(const size_t &i) const { return i == 0 ? p.size() - 1 : i - 1; }

    db C() const
    {
        db sum = 0;
        for (size_t i = 0; i < p.size(); i++)
            sum += p[i].dis(p[nxt(i)]);
        return sum;
    }

    db S() const
    {
        db sum = 0;
        for (size_t i = 0; i < p.size(); i++)
            sum += p[i] ^ p[nxt(i)];
        return abs(sum) / 2;
    }

    // 判断点是否在凸多边形内
    // 复杂度 O(logn)
    // -1 点在多边形边上 | 0 点在多边形外 | 1 点在多边形内
    int is_in(const Point &a) const
    {
        const auto &p = this->p;
        if (p.size() == 1)
            return a == p[0] ? -1 : 0;
        if (p.size() == 2)
            return Segment(p[0], p[1]).is_on(a) ? -1 : 0;
        if (a == p[0])
            return -1;
        if ((p[1] - p[0]).toleft(a - p[0]) == -1 || (p.back() - p[0]).toleft(a - p[0]) == 1)
            return 0;
        const auto cmp = [&](const Point &u, const Point &v)
        { return (u - p[0]).toleft(v - p[0]) == 1; };
        const size_t i = lower_bound(p.begin() + 1, p.end(), a, cmp) - p.begin();
        if (i == 1)
            return Segment{p[0], p[i]}.is_on(a) ? -1 : 0;
        if (i == p.size() - 1 && Segment{p[0], p[i]}.is_on(a))
            return -1;
        if (Segment{p[i - 1], p[i]}.is_on(a))
            return -1;
        return (p[i] - p[i - 1]).toleft(a - p[i - 1]) > 0;
    }

    pair<int, int> get_tan(const Point &a)
    {
        if (is_in(a) != 0)
            return {-2, -2};
        if (p.size() == 1)
            return {0, 0};
        int n = p.size(), l = 0, r = n;
        int ansl = -1, ansr = -1;
        auto isleft = [a, this](int i, int j) -> bool
        {
            return ((p[i] - a) ^ (p[j] - a)) > 0;
        };
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (isleft(mid, pre(mid)) && !isleft(nxt(mid), mid))
            {
                ansr = mid;
                break;
            }
            if (isleft(nxt(mid), mid) && !isleft(nxt(nxt(mid)), nxt(mid)))
            {
                ansr = nxt(mid);
                break;
            }
            if (isleft(nxt(l), l))
            {
                if (!isleft(nxt(mid), mid))
                    r = mid;
                else if (isleft(mid, l))
                    l = mid;
                else
                    r = mid;
            }
            else
            {
                if (isleft(nxt(mid), mid))
                    l = mid;
                else if (isleft(mid, l))
                    r = mid;
                else
                    l = mid;
            }
        }
        l = 0, r = n;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (!isleft(mid, pre(mid)) && isleft(nxt(mid), mid))
            {
                ansl = mid;
                break;
            }
            if (!isleft(nxt(mid), mid) && isleft(nxt(nxt(mid)), nxt(mid)))
            {
                ansl = nxt(mid);
                break;
            }
            if (!isleft(nxt(l), l))
            {
                if (isleft(nxt(mid), mid))
                    r = mid;
                else if (!isleft(mid, l))
                    l = mid;
                else
                    r = mid;
            }
            else
            {
                if (!isleft(nxt(mid), mid))
                    l = mid;
                else if (!isleft(mid, l))
                    r = mid;
                else
                    l = mid;
            }
        }
        return {ansl, ansr};
    }
};

#define back1(x) x.back()
#define back2(x) *(x.rbegin() + 1)

// Andrew
Polygon convex(vector<Point> p)
{
    vector<Point> st;
    sort(p.begin(), p.end());
    for (Point u : p)
    {
        while (st.size() > 1 && (back1(st) - back2(st)).toleft(u - back2(st)) <= 0)
            st.pop_back();
        st.push_back(u);
    }
    size_t k = st.size();
    p.pop_back();
    reverse(p.begin(), p.end());
    for (Point u : p)
    {
        while (st.size() > k && (back1(st) - back2(st)).toleft(u - back2(st)) <= 0)
            st.pop_back();
        st.push_back(u);
    }
    st.pop_back();
    return Polygon(st);
}

Polygon P;
vp ps;
int n, Q;

inline void solve()
{
    cin >> n >> Q;
    ps.resize(n);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        ps[i - 1] = Point(x, y);
    }
    P = convex(ps);

    while (Q--)
    {
        int qx1, qy1, qx2, qy2;
        cin >> qx1 >> qy1 >> qx2 >> qy2;
        Point qu = Point(qx1, qy1), qv = Point(qx2, qy2);
        // case 1
        int ku = P.is_in(qu), kv = P.is_in(qv);
        if (ku == -1 || kv == -1 || ku + kv == 1)
        {
            cout << "YES\n";
            continue;
        }
        if (ku == 1 && kv == 1)
        {
            cout << "NO\n";
            continue;
        }
        // case 2
        auto tu = P.get_tan(qu), tv = P.get_tan(qv);
        map<int, int> vis;
        vis[tu.first]++, vis[tu.second]--;
        vis[tv.first]++, vis[tv.second]--;
        if (tu.first > tu.second)
            vis[n]--, vis[0]++;
        if (tv.first > tv.second)
            vis[n]--, vis[0]++;
        int cnt = 0, _2 = false;
        for(auto [pos, v] : vis)
        {
            cnt += v;
            _2 = (_2 || (cnt >= 2));
        }
        if (_2)
        {
            cout << "NO2\n";
            continue;
        }
        auto vs = qv - qu;
        auto vl = P.p[tu.first] - qu, vr = P.p[tu.second] - qu;
        if ((vl ^ vs) <= 0 && (vs ^ vr) <= 0)
            cout << "YES\n";
        else 
            cout << "NO3\n";
    }
}

int main()
{
// #define MULTIPLE_CASE
#define CLOSE_IOS
#ifdef CLOSE_IOS
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
    int Test = 1;
#ifdef MULTIPLE_CASE
#ifdef CLOSE_IOS
    cin >> Test;
#else
    scanf("%d", &Test);
#endif
#endif
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3520kb

input:

4 6
1 1
4 1
4 4
1 4
0 2 2 0
0 1 1 1
0 0 5 5
2 2 4 2
2 2 3 2
5 1 0 2

output:

YES
YES
YES
YES
NO
YES

result:

ok 6 token(s): yes count is 5, no count is 1

Test #2:

score: -100
Wrong Answer
time: 60ms
memory: 3612kb

input:

20 200000
8838 9219
12190 11292
15953 7581
16690 6159
21104 5484
8978 1076
4354 1065
1261 676
12684 14159
15469 22416
13493 28027
15531 26837
18253 26053
26444 24253
22160 19958
24879 12856
28793 22156
25300 10245
14749 15078
12946 13942
26544 28338 18806 21279
5592 29200 20935 25253
28189 17513 215...

output:

YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO2
YES
YES
YES
YES
NO
YES
YES
NO
NO3
YES
NO
YES
NO
YES
YES
YES
NO
NO
NO
YES
YES
YES
YES
YES
NO
YES
NO2
NO2
YES
NO
YES
YES
NO
NO2
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO2
YES
NO2
YES
NO
YES
YES
YES
YES
YES
NO
NO2
YES
NO
YES
YES
NO...

result:

wrong answer expected YES, found NO [4th token]