QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#549963#6403. Master of PolygonpandapythonerWA 1ms4184kbC++238.6kb2024-09-07 03:04:562024-09-07 03:04:56

Judging History

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

  • [2024-09-07 03:04:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4184kb
  • [2024-09-07 03:04:56]
  • 提交

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-9;


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;
    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);
    }
    vector<bool> result(q, true);
    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 (it != st.begin()) {
                if (intersects_tuples(*it, *prev(it))) {
                    --it;
                }
            }
            if (it != st.end()) {
                if (intersects_tuples(*it, *next(it))) {
                    int i = get<2>(*it);
                    if (i < n) {
                        it = next(it);
                        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: 0
Wrong Answer
time: 1ms
memory: 4184kb

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
NO
YES
YES
NO
YES

result:

wrong answer expected YES, found NO [2nd token]