QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#289497#7862. Land Tradeucup-team055WA 1ms4868kbC++236.1kb2023-12-23 18:00:012023-12-23 18:00:02

Judging History

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

  • [2023-12-23 18:00:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4868kb
  • [2023-12-23 18:00:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define all(a) begin(a), end(a)
template<class T> bool chmin(T& a, T b) { if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, T b) { if(a >= b) return 0; a = b; return 1; }

using Line = array<ll, 3>;
using Bit = bitset<1 << 19>;
vector<Line> lines;
vector<tuple<double, double, double>> polygons;
enum OP {
    AND,
    OR,
    XOR,
    NOT,
    PLANE
};
Bit plane(Line* p) {
    Bit bit;
    auto [a, b, c] = *p;
    rep(i, 0, polygons.size()) {
        auto [x, y, S] = polygons[i];
        if(x * a + y * b + c > 0) bit[i] = 1;
    }
    return bit;
}
double area(Bit bit) {
    long double ans;
    rep(i, 0, polygons.size()) {
        auto [x, y, S] = polygons[i];
        if(bit[i]) ans += S;
    }
    return ans;
}
struct tree {
    OP type;
    tree *l = nullptr, *r = nullptr;
    Bit ans() const {
        if(type == AND) return l->ans() & r->ans();
        if(type == OR) return l->ans() | r->ans();
        if(type == XOR) return l->ans() ^ r->ans();
        if(type == NOT) return ~r->ans();
        if(type == PLANE) return plane((Line*)r);
        abort();
    }
};
void get(const char*& p, char c) {
    assert(*p == c);
    p++;
}
ll decimal(const char*& p) {
    int x = 0;
    bool neg = 0;
    if(*p == '-') {
        neg = 1;
        get(p, '-');
    }
    assert(isdigit(*p));
    while(isdigit(*p)) {
        x *= 10;
        x += *p - 48;
        p++;
    }
    if(neg) x *= -1;
    return x;
}
tree* formula(const char*& p) {
    if(*p == '[') {
        get(p, '[');
        const ll a = decimal(p);
        get(p, ',');
        const ll b = decimal(p);
        get(p, ',');
        const ll c = decimal(p);
        get(p, ']');
        lines.push_back({a, b, c});
        return new tree{PLANE, nullptr, (tree*)new Line{a, b, c}};
    }
    get(p, '(');
    if(*p == '!') {
        get(p, '!');
        auto r = formula(p);
        get(p, ')');
        return new tree{NOT, nullptr, r};
    }
    auto l = formula(p);
    const OP op = [&]{
        if(*p == '&') return AND;
        if(*p == '|') return OR;
        if(*p == '^') return XOR;
        abort();
    }();
    p++;
    auto r = formula(p);
    get(p, ')');
    return new tree{op, l, r};
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll x1, x2, y1, y2;
    cin >> x1 >> x2 >> y1 >> y2;
    lines.push_back({-1, 0, x1});
    lines.push_back({1, 0, x2});
    lines.push_back({0, -1, y1});
    lines.push_back({0, -1, y2});
    string S;
    cin >> S;
    auto p = S.c_str();
    auto tree = formula(p);

    // unique lines
    for(auto& [a, b, c] : lines) {
        ll g = gcd(gcd(a, b), c);
        if(pair{a, b} < pair{0LL, 0LL}) g *= -1;
        a /= g;
        b /= g;
        c /= g;
    }
    ranges::sort(lines);
    {
        auto [mid, end] = ranges::unique(lines);
        lines.erase(mid, end);
    }
    ranges::sort(lines, [](auto a, auto b) { return a[0] * b[1] - a[1] * b[0] > 0; });

    // calc points
    vector<array<ll, 3>> points;
    rep(i, 0, lines.size()) rep(j, 0, i) {
        auto [a1, b1, c1] = lines[i];
        auto [a2, b2, c2] = lines[j];
        ll Q = a1 * b2 - b1 * a2;
        if(Q == 0) continue;
        // (b2 a1 - b1 a2) x + (b2 c1 - b1 c2) = 0
        // (a2 b1 - a1 b2) y + (a2 c1 - a1 c2) = 0
        ll X = -(b2 * c1 - b1 * c2);
        ll Y = a2 * c1 - a1 * c2;
        ll g = gcd(Q, gcd(X, Y));
        if(Q < 0) g *= -1;
        Q /= g;
        X /= g;
        Y /= g;
        if(x1 * Q > X || X > x2 * Q || y1 * Q > Y || Y > y2 * Q) continue;
        points.push_back({X, Y, Q});
    }

    ranges::sort(points);
    {
        auto [mid, end] = ranges::unique(points);
        points.erase(mid, end);
    }

    const ll n = points.size();
    vector g(n, vector<tuple<ll, ll, bool>>{});
    vector<ll> idx(n);
    for(auto [a, b, c] : lines) {
        ll prev = -1;
        rep(i, 0, n) {
            auto [x, y, q] = points[i];
            if(a * x + b * y + c * q) continue;
            if(prev != -1) g[prev].push_back({i, -1, false});
            prev = i;
        }
    }
    for(auto [a, b, c] : lines) {
        ll prev = -1;
        for(ll i = n; i--; ) {
            auto [x, y, q] = points[i];
            if(a * x + b * y + c * q) continue;
            if(prev != -1) {
                const ll j = idx[i]++;
                assert(get<0>(g[i][j]) == prev);
                get<1>(g[i][j]) = g[prev].size();
                g[prev].push_back({i, j, false});
            }
            prev = i;
        }
    }

    bool one = 1;
    // find polygons
    rep(i, 0, n) {
        rep(j, 0, g[i].size()) if(!get<2>(g[i][j])) {
            vector<ll> polygon;
            do {
                polygon.push_back(i);
                auto& [to, rev, used] = g[i][j];
                i = to;
                j = rev - 1;
                if(j < 0) j += g[i].size();
                used = 1;
            } while(!get<2>(g[i][j]));
            double S = 0, X = 0, Y = 0;
            const ll m = polygon.size();
            polygon.push_back(0);
            rep(k, 0, m) {
                auto [x1, y1, q1] = points[polygon[k]];
                auto [x2, y2, q2] = points[polygon[k + 1]];
                double X1 = (double)x1 / q1;
                double Y1 = (double)y1 / q1;
                double X2 = (double)x2 / q2;
                double Y2 = (double)y2 / q2;
                S -= X1 * Y2 - Y1 * X2;
                X += X1;
                Y += Y1;
            }
            if(S < 0) {
                if(one) {
                    one = 0;
                    continue;
                }
                else abort();
            }
            X /= m;
            Y /= m;
            polygons.push_back({X, Y, S});
        }
    }

    cout.precision(10);
    cout << area(tree->ans()) << endl;
}
/*
-5 10 -10 5
((!([1,2,-3]&[10,3,-2]))^([-2,3,1]|[5,-2,7]))
70.451693404634582
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

0.5

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 4868kb

input:

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

output:

0

result:

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