QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#549968#6403. Master of PolygonpandapythonerTL 1ms4224kbC++239.3kb2024-09-07 03:42:472024-09-07 03:42:47

Judging History

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

  • [2024-09-07 03:42:47]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4224kb
  • [2024-09-07 03:42:47]
  • 提交

answer

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

using ll = long long;
using ld = long double;

#define len(a) int((a).size())
#define all(a) begin(a), end(a)
#define rep(i, n) for (int i = 0; i < (n); i++)



mt19937 rnd(234234);
ld pi = atan2l(0, -1);

struct vec {
    ld x, y;
    vec() : x(0), y(0) {}
    vec(ld x, ld y) : x(x), y(y) {}

    ld length2() const {
        return x * x + y * y;
    }

    ld length() const {
        return sqrtl(length());
    }


    void rotate(ld alpha) {
        ld asin = sinl(alpha), acos = cosl(alpha);
        ld nx = x * acos - y * asin;
        ld ny = y * acos + x * asin;
        x = nx;
        y = ny;
    }
};


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


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


ld operator*(const vec& a, const vec& b) {
    return a.x * b.x + a.y * b.y;
}

vec operator*(ld a, const vec& b) {
    return vec{ a * b.x, a * b.y };
}


ld operator%(const vec& a, const vec& b) {
    return a.x * b.y - a.y * b.x;
}


ld eps = 1e-8;


int sign(ld x) {
    if (abs(x) < eps) return 0;
    return x > 0 ? 1 : -1;
}


bool intersects(const vec& a, const vec& b, const vec& c, const vec& d, bool collinear_bad = false) {
    if (abs((a - b) % (c - d)) < eps) {
        if (collinear_bad) return false;
        if (abs((b - a) % (c - a)) >= eps) return false;
        if (max((b - a) * (c - a), (b - a) * (d - a)) < -eps) return false;
        if (max((a - b) * (c - b), (a - b) * (d - b)) < -eps) return false;
        return true;
    }
    if (sign((b - a) % (c - a)) * sign((b - a) % (d - a)) > 0) return false;
    if (sign((d - c) % (a - c)) * sign((d - c) % (b - c)) > 0) return false;
    return true;
}


vec intersect(const vec& a, const vec& b, const vec& c, const vec& d) {
    vec t = a - b;
    swap(t.x, t.y);
    t.x = -t.x;
    assert(abs(t * a - t * b) <= eps);
    ld need = t * a;
    ld start = t * c;
    ld finish = t * d;
    assert(min(start, finish) - eps <= need and need <= max(start, finish) + eps);
    ld alpha = (need - start) / (finish - start);
    vec result = (1 - alpha) * c + alpha * d;
    assert(abs(t * result - need) < eps);
    return result;
}


ld get_val(vec a, vec b, ld x) {
    if (a.x > b.x) swap(a, b);
    assert(a.x + eps < x and x + eps < b.x);
    ld alpha = (x - a.x) / (b.x - a.x);
    ld result = a.y * (1 - alpha) + b.y * alpha;
    return result;
}


const int block_len = 300;

int n, q;
vector<pair<vec, vec>> poly;
vector<pair<vec, vec>> tasks;
ld cur_x = 0;


struct compare {
    bool operator()(const tuple<vec, vec, int>& p, const tuple<vec, vec, int>& q) const {
        auto [a, b, i] = p;
        auto [c, d, j] = q;
        ld yi = get_val(a, b, cur_x);
        ld yj = get_val(c, d, cur_x);
        if (abs(yi - yj) > eps) {
            return yi < yj;
        }
        return i < j;
    }
};


signed main() {
    cerr << pi << endl;
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> q;
    poly.resize(n);
    rep(i, n) {
        vec a;
        cin >> a.x >> a.y;
        poly[i].first = a;
        poly[(n + i - 1) % n].second = a;
    }
    tasks.resize(q);
    rep(i, q) {
        cin >> tasks[i].first.x >> tasks[i].first.y >> tasks[i].second.x >> tasks[i].second.y;
    }
    ld alpha = rnd() % int(1e9) / (1e9) * 2 * pi;
    // alpha = 0.02;
    cerr << "alpha: " << alpha << endl;
    vector<bool> result(q, true);
    set<pair<int, int>> endpoints;
    rep(i, n) {
        endpoints.insert(make_pair((int)roundl(poly[i].first.x), (int)roundl(poly[i].first.y)));
    }
    assert(len(endpoints) == n);
    rep(i, q) {
        auto biba = make_pair((int)round(tasks[i].first.x), (int)roundl(tasks[i].first.y));
        auto boba = make_pair((int)round(tasks[i].second.x), (int)roundl(tasks[i].second.y));
        if (endpoints.find(biba) != endpoints.end() or endpoints.find(boba) != endpoints.end()) {
            result[i] = false;
        }
    }
    rep(i, n) {
        poly[i].first.rotate(alpha);
        poly[i].second.rotate(alpha);
    }
    rep(i, q) {
        tasks[i].first.rotate(alpha);
        tasks[i].second.rotate(alpha);
    }
    for (int l = 0; l < q; l += block_len) {
        int r = min(q, l + block_len);
        vector<ld> points;
        rep(i, n) points.push_back(poly[i].first.x);
        for (int i = l; i < r; i += 1) {
            points.push_back(tasks[i].first.x);
            points.push_back(tasks[i].second.x);
            auto [a, b] = tasks[i];
            for (int j = i + 1; j < r; j += 1) {
                auto [c, d] = tasks[j];
                if (intersects(a, b, c, d, true)) {
                    points.push_back(intersect(a, b, c, d).x);
                }
            }
        }
        sort(all(points));
        int cur = 0;
        for (int i = 1; i < len(points); i += 1) {
            if (abs(points[i] - points[cur]) > eps) {
                points[++cur] = points[i];
            }
        }
        points.resize(cur + 1);
        int m = len(points);
        assert(m >= 2);
        vector<vector<int>> to_insert(m - 1), to_erase(m - 1);
        auto get_pos = [&](ld x) {
            auto it = upper_bound(all(points), x + eps);
            assert(it != points.begin());
            int i = it - points.begin() - 1;
            assert(abs(points[i] - x) < eps);
            return i;
            };
        rep(i, n) {
            auto [a, b] = poly[i];
            int pa = get_pos(a.x), pb = get_pos(b.x);
            assert(pa != pb);
            if (pa > pb) swap(pa, pb);
            to_insert[pa].push_back(i);
            to_erase[pb - 1].push_back(i);
        }
        for (int i = l; i < r; i += 1) {
            auto [a, b] = tasks[i];
            int pa = get_pos(a.x), pb = get_pos(b.x);
            assert(pa != pb);
            if (pa > pb) swap(pa, pb);
            to_insert[pa].push_back(n + i);
            to_erase[pb - 1].push_back(n + i);
            for (int j = l; j < r; j += 1) {
                if (i == j) continue;
                auto [c, d] = tasks[j];
                if (intersects(a, b, c, d, true)) {
                    ld x = intersect(a, b, c, d).x;
                    int pos = get_pos(x);
                    if (pos > pa and pos < pb) {
                        to_erase[pos - 1].push_back(n + i);
                        to_insert[pos].push_back(n + i);
                    }
                }
            }
        }
        set<tuple<vec, vec, int>, compare> st;
        vector<bool> inserted(n + q, false);
        auto intersects_tuples = [&](const tuple<vec, vec, int>& p, const tuple<vec, vec, int>& q) {
            auto& [a, b, i] = p;
            auto& [c, d, j] = q;
            return ((i >= n) != (j >= n)) and intersects(a, b, c, d);
            };
        function<void(int)> insert;
        function<void(int)> erase;
        function<void(decltype(st)::iterator)> check;
        check = [&](decltype(st)::iterator it) {
            if (it == st.end()) return;
            if (get<2>(*it) < n) {
                if (it != st.begin() and get<2>(*prev(it)) >= n) {
                    check(prev(it));
                }
                if (next(it) != st.end() and get<2>(*next(it)) >= n) {
                    check(next(it));
                }
                return;
            }
            bool bad = false;
            if (!bad and it != st.begin() and intersects_tuples(*it, *prev(it))) bad = true;
            if (!bad and next(it) != st.end() and intersects_tuples(*it, *next(it))) bad = true;
            if (bad) {
                int i = get<2>(*it);
                assert(i >= n);
                auto nit = it != st.begin() ? prev(it) : next(it);
                inserted[i] = false;
                result[i - n] = false;
                st.erase(it);
                check(nit);
            }
            };
        erase = [&](int i) {
            if (!inserted[i]) return;
            vec a, b;
            if (i < n) {
                tie(a, b) = poly[i];
            } else {
                tie(a, b) = tasks[i - n];
            }
            auto it = st.find(make_tuple(a, b, i));
            assert(it != st.end());
            auto nit = it != st.begin() ? prev(it) : next(it);
            st.erase(it);
            inserted[i] = false;
            check(nit);
            };
        insert = [&](int i) {
            if (inserted[i]) return;
            if (i >= n and !result[i - n]) return;
            vec a, b;
            if (i < n) {
                tie(a, b) = poly[i];
            } else {
                tie(a, b) = tasks[i - n];
            }
            auto it = st.emplace(a, b, i).first;
            inserted[i] = true;
            check(it);
            };
        rep(i, m - 1) {
            cur_x = (points[i] + points[i + 1]) / 2;
            for (auto pos : to_insert[i]) insert(pos);
            for (auto pos : to_erase[i]) erase(pos);
        }
    }
    rep(i, q) {
        if (!result[i]) cout << "YES" << "\n";
        else cout << "NO" << "\n";
    }
    return 0;
}


/*
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

*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4224kb

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
Time Limit Exceeded

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:


result: