QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#375660 | #7862. Land Trade | darkseba | WA | 1ms | 3848kb | C++20 | 5.5kb | 2024-04-03 14:36:51 | 2024-04-03 14:36:53 |
Judging History
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: 1ms
memory: 3848kb
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'