QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#289497 | #7862. Land Trade | ucup-team055 | WA | 1ms | 4868kb | C++23 | 6.1kb | 2023-12-23 18:00:01 | 2023-12-23 18:00:02 |
Judging History
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'