QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#375659#7862. Land TradedarksebaWA 0ms3968kbC++235.5kb2024-04-03 14:36:342024-04-03 14:36:35

Judging History

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

  • [2024-04-03 14:36:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3968kb
  • [2024-04-03 14:36:34]
  • 提交

answer

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = (b); a < (c); a++)
#define all(x) begin(x), end(x)
#define sz(x) int(size(x))
using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;

const double eps = 1e-9;

template<class T>
struct Point {
    using P = Point;
    T x, y;
    explicit Point(T x=0, T xy=0): x(x), y(y) {}
    P operator+(P p) const { return P(x+p.x, y+p.y); }
    P operator-(P p) const { return P(x-p.x, y-p.y); }
    P operator*(T d) const { return P(x*d, y*d); }
    P operator/(T d) const { return P(x/d, y/d); }
    T dot(P p) const { return x*p.x + y*p.y; }
    T cross(P p) const { return x*p.y - y*p.x; }
    T cross(P a, P b) const { return (a-*this).cross(b-*this); }
};

template<class P>
pair<int, P> lineInter(P s1, P e1, P s2, P e2) {
    auto d = (e1 - s1).cross(e2 - s2);
    if (d == 0)
        return {-(s1.cross(e1, s2) == 0), P(0, 0)};
    auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
    return {1, (s1 * p + e1 * q) / d};
}

typedef Point<double> P;
vector<P> polygonCut(const vector<P>& poly, P s, P e) {
    vector<P> res;
    rep (i, 0, sz(poly)) {
        P cur = poly[i], prev = i ? poly[i-1] : poly.back();
        bool side = s.cross(e, cur) < 0;
        if (side != (s.cross(e, prev) < 0))
            res.push_back(lineInter(s, e, cur, prev).second);
        if (side) res.push_back(cur);
    }
    return res;
}

template<class T>
T polygonArea2(vector<Point<T>>& v) {
    T a = v.back().cross(v[0]);
    rep (i, 0, sz(v) - 1) a += v[i].cross(v[i+1]);
    return a;
}

vector<pair<char, int>> stk;
int ptr = 0;
pair<char, int> pop() { return stk[ptr++]; }
pair<char, int> peek() { return stk[ptr]; }

map<tuple<int, int, int>, int> id;
vector<tuple<int, int, int>> lines;

const int GRPS = 301 * 301 / 2;
using bs = bitset<GRPS>;

vector<pair<vector<P>, vector<bool>>> polys;

vector<tuple<char, int, int>> nodes;
int parse() {
    auto [ch, li] = pop();

    if (ch == '(') {
        if (peek().first == '!') {
            pop();
            auto x = parse();
            int u = sz(nodes);
            assert(pop().first == ')');

            nodes.emplace_back('!', x, -1);
            return u;
        }
        
        auto x = parse();
        auto op = pop().first;
        auto y = parse();
        assert(pop().first == ')');

        int u = sz(nodes);
        nodes.emplace_back(op, x, y);
        return u;
    }
    
    assert(ch == 0);
    // return [&](int p) -> bool { 
    //     // auto [a, b, c] = lines[li];
    //     // return a*p.x + b*p.y + c > 0;
    //     cout << "query polygon " << p << " li " << li << endl;
    //     return polys[p].second[li];
    // };

    int u = sz(nodes);
    nodes.emplace_back(0, -1, li);
    return u;
    // bs x;
    // rep (i, 0, sz(polys))
    //     x[i] = polys[i].second[li];
    
    // return x;
}

bool dfs(int p, int u) {
    auto [op, l, r] = nodes[u];
    if (op == 0) return polys[p].second[r];
    if (op == '!') return !dfs(p, l);
    if (op == '&') return dfs(p, l) && dfs(p, r);
    if (op == '|') return dfs(p, l) || dfs(p, r);
    if (op == '^') return dfs(p, l) ^ dfs(p, r);
    assert(0);
    return 0;
}

void solve() {
    ll xlo, xhi, ylo, yhi;
    cin >> xlo >> xhi >> ylo >> yhi;

    string in;
    cin >> in;

    for (int i = 0; i < sz(in); ) {
        if (in[i] != '[') {
            stk.emplace_back(in[i++], 0);
            continue;
        }
        
        i++;

        int k = 0;
        while (in[i+k] != ',') k++;
        int a = stoi(in.substr(i, k));
        i += k + 1;

        k = 0;
        while (in[i+k] != ',') k++;
        int b = stoi(in.substr(i, k));
        i += k + 1;

        k = 0;
        while (in[i+k] != ']') k++;
        int c = stoi(in.substr(i, k));
        i += k + 1;

        int idx = sz(lines);
        lines.emplace_back(a, b, c);
        id[lines[idx]] = idx;
        stk.emplace_back(0, idx);
    }
    
    polys.push_back({{P(xlo, ylo), P(xhi, ylo), P(xhi, yhi), P(xlo, yhi)}, vector<bool>(sz(lines))});
    vector<pair<vector<P>, vector<bool>>> nxt;
    nxt.reserve(sz(lines) * sz(lines) * 1.5 + 100);

    rep (i, 0, sz(lines)) {
        auto [a, b, c] = lines[i];

        nxt.clear();

        P dir(b, -a), p0;

        if (a != 0) p0 = P(double(-c) / a);
        else p0 = P(0, double(-c) / b);

        auto p1 = p0 + dir;

        for (auto& [poly, sides] : polys) {
            auto res = polygonCut(poly, p0, p1);
            if (!res.empty()) {
                nxt.push_back({res, sides});
                nxt.back().second[i] = 0;
            }
            res = polygonCut(poly, p1, p0);
            if (!res.empty()) {
                nxt.push_back({res, sides});
                nxt.back().second[i] = 1;
            }
        }

        swap(polys, nxt);
    }

    assert(sz(polys) < GRPS);
    auto root = parse();

    double ans = 0;
    rep (i, 0, sz(polys)) {
        auto area = polygonArea2(polys[i].first);

        if (dfs(i, root))
            ans += area;
    }

    ans /= 2;

    cout << setprecision(15) << fixed << ans << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    // int t; cin >> t; while (t--)
    solve();

    return 0;
}

/*

-5 10 -10 5
((!([1,2,-3]&[10,3,-2]))^([-2,3,1]|[5,-2,7]))

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3968kb

input:

0 1 0 1
([-1,1,0]^[-1,-1,1])

output:

0.000000000000000

result:

wrong answer 1st numbers differ - expected: '0.5000000', found: '0.0000000', error = '0.5000000'