QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402618#7862. Land Tradeu2x1WA 1ms3984kbC++206.8kb2024-05-01 02:03:382024-05-01 02:03:39

Judging History

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

  • [2024-05-01 02:03:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3984kb
  • [2024-05-01 02:03:38]
  • 提交

answer

#include "bits/stdc++.h"

#define all(x)   x.begin(), x.end()
#define NL       std::cout << '\n'

using lnt = long long;

const int inf = 0x3f3f3f3f;
const lnt linf = 1ll << 62;

using db = long double; const db eps = 1e-12;
int sgn(db x) { return (x < -eps ? -1 : x > eps); }

struct Pt { db x, y; };
std::istream& operator>>(std::istream& is, Pt &p) {
  int x, y; std::cin >> x >> y;
  p.x = x; p.y = y; return is;
}
std::ostream& operator<<(std::ostream& os, Pt p) {
	return os << "(" << p.x << "," << p.y << "),";
}

Pt operator-(Pt a, Pt b) { return { a.x - b.x, a.y - b.y }; }
Pt operator+(Pt a, Pt b) { return { a.x + b.x, a.y + b.y }; }
Pt operator*(Pt a, db x) { return { a.x * x, a.y * x }; }
Pt operator/(Pt a, db x) { return { a.x / x, a.y / x }; }
db dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y; }
db det(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }
bool operator==(Pt a, Pt b) { return !sgn(dot(a-b, a-b)); }
bool operator!=(Pt a, Pt b) { return sgn(dot(a-b, a-b)); }
bool operator<(Pt a, Pt b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }

struct Line { Pt s, t; };
Pt intersect(Line a, Line b) {
  db v = det(a.t - a.s, b.s - a.s);
  db u = det(a.t - a.s, b.t - a.s);
  return (b.s * u - b.t * v) / (u - v);
}
bool para(Line a, Line b) {
  return !sgn(det(a.t - a.s, b.t - b.s));
}

std::pair<std::vector<Pt>, std::vector<Pt>> hullCut(std::vector<Pt> &hull, Line a) {
  int l = -1, r = -1;
  Pt il, ir;
  for (int i = hull.size() - 1, j = 0; j < hull.size(); i = j++) {
    auto &u = hull[i], &v = hull[j];
    int s1 = side(a.s, a.t, u), s2 = side(a.s, a.t, v);
    if (para({hull[i], hull[j]}, a)) { assert(1); return {hull, {}}; }
    if (s1 * s2 <= 0) {
      if (l == -1) { l = j; il = intersect({u, v}, a); }
      else {
        Pt inter = intersect({u, v}, a);
        if (inter != il) { r = j; ir = inter; }
      }
    }
  }
  if (r == -1) { return { hull, {} }; }
  std::vector<Pt> lhs(hull.begin() + l, hull.begin() + r);
  if (lhs.empty() || (ir != lhs.back() && ir != lhs.front())) { lhs.emplace_back(ir); }
  if (lhs.empty() || (il != lhs.back() && il != lhs.front())) { lhs.emplace_back(il); }
  std::vector<Pt> rhs(hull.begin() + r, hull.end()); rhs.insert(rhs.end(), hull.begin(), hull.begin() + l);
  if (rhs.empty() || (il != rhs.back() && il != rhs.front())) { rhs.emplace_back(il); }
  if (rhs.empty() || (ir != rhs.back() && ir != rhs.front())) { rhs.emplace_back(ir); }
  return {lhs, rhs};
}

enum { ATOM = 128, AND, OR, XOR, NOT };

Pt polyCenter(std::vector<Pt> &v) {
  Pt ret {0, 0}; db s = 0;
  for (int j = 0, i = v.size() - 1; j < v.size(); i = j++) {
    ret = ret + (v[i] + v[j]) * det(v[i], v[j]);
    s += det(v[i], v[j]);
  }
  return ret / s / 3;
}

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cout << std::fixed << std::setprecision(15);
  std::vector<std::vector<Pt>> polys(1);
  {
    int xmi, xmx, ymi, ymx; std::cin >> xmi >> xmx >> ymi >> ymx;
    polys[0].push_back({(db)xmi, (db)ymx});
    polys[0].push_back({(db)xmi, (db)ymi});
    polys[0].push_back({(db)xmx, (db)ymi});
    polys[0].push_back({(db)xmx, (db)ymx});
  }
  std::string raw; std::cin >> raw;

  Line tokenVal; int token;
  int p = 0;

  auto next = [&]() -> void {
    while (p != raw.size()) {
      token = raw[p++];
      if (token == '[') {
        static auto read = [&]() {
          int ret = 0; bool neg = 0;
          while (raw[p] == '-' || raw[p] == '+' || (raw[p] >= '0' && raw[p] <= '9')) {
            if (raw[p] == '-') { neg = !neg; }
            else if (raw[p] == '+') {  }
            else { ret = ret * 10 + raw[p] - '0'; }
            ++p;
          }
          if (neg) { ret = -ret; }
          return ret;
        };
        int a = read();
        ++p; // parse ','
        int b = read();
        ++p; // parse ','
        int cc = read();
        ++p; // parse ']'
        token = ATOM;
        if (b == 0) {
          tokenVal.s = { -1.L * cc / a, 0 };
          tokenVal.t = { -1.L * cc / a, (a > 0 ? -1. : 1.) };
        } else {
          tokenVal.s = { 0, -1.L * cc / b };
          tokenVal.t = tokenVal.s + Pt{ 1, -1.L * a / b };
        }
        if (b < 0) { std::swap(tokenVal.s, tokenVal.t); }
        return;
      } else if (token == '&') {
        token = AND; return;
      } else if (token == '|') {
        token = OR; return;
      } else if (token == '^') {
        token = XOR; return;
      } else if (token == '!') {
        token = NOT; return;
      } else if (token == '(' || token == ')') {
        return;
      }
    }
  };

  auto expr1 = [&](auto &self, int level) -> void {
    if (token == ATOM) {
      std::vector<std::vector<Pt>> npolys; npolys.reserve(polys.size() * 2);
      for (auto poly : polys) {
        auto [a, b] = hullCut(poly, tokenVal);
        npolys.emplace_back(a);
        if (!b.empty()) { npolys.emplace_back(b); }
      }
      std::swap(npolys, polys);
      next();
    } else if (token == '(') {
      next();
      self(self, ATOM);
      next();
    } else if (token == NOT) {
      next();
      self(self, NOT);
    }

    while (token >= level) {
      if (token == AND) {
        next(); self(self, NOT);
      } else if (token == OR) {
        next(); self(self, NOT);
      } else if (token == XOR) {
        next(); self(self, NOT);
      } else if (token == NOT) {
        next(); self(self, NOT);
      }
    }
  };

  next(); expr1(expr1, ATOM);

  std::vector<bool> stk;
  Pt ct;
  auto expr2 = [&](auto &self, int level) -> void {
    if (token == ATOM) {
      stk.emplace_back(side(tokenVal.s, tokenVal.t, ct) >= 0);
      next();
    } else if (token == '(') {
      next();
      self(self, ATOM);
      next();
    } else if (token == NOT) {
      next();
      self(self, NOT);
      stk.back() = !stk.back();
    }

    while (token >= level) {
      if (token == AND) {
        next(); self(self, NOT);
        bool a = stk.back(); stk.pop_back();
        bool b = stk.back(); stk.pop_back();
        stk.emplace_back(a & b);
      } else if (token == OR) {
        next(); self(self, NOT);
        bool a = stk.back(); stk.pop_back();
        bool b = stk.back(); stk.pop_back();
        stk.emplace_back(a | b);
      } else if (token == XOR) {
        next(); self(self, NOT);
        bool a = stk.back(); stk.pop_back();
        bool b = stk.back(); stk.pop_back();
        stk.emplace_back(a ^ b);
      }
    }
  };

  db ret = 0;
  for (auto poly : polys) {
    ct = polyCenter(poly);
    p = 0; next(); expr2(expr2, ATOM);
    if (stk.back()) {
      for (int i = poly.size() - 1, j = 0; j < poly.size(); i = j++) {
        ret += det(poly[i], poly[j]);
      }
    }
    stk.pop_back();
  }

  std::cout << ret / 2;
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3872kb

input:

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

output:

0.500000000000000

result:

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

Test #2:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

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

output:

70.451693404634581

result:

ok found '70.4516934', expected '70.4516934', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

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

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

0 1000 0 1000
(([1,-1,0]&[-1000,999,999])&([1,0,-998]&[0,1,-998]))

output:

0.000500000000073

result:

ok found '0.0005000', expected '0.0005000', error '0.0000000'

Test #5:

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

input:

-725 165 643 735
((((!(([22,15,137]|(!([23,-5,-41]^(!([2,25,-515]&[-37,10,487])))))&(!(([25,24,47]^([-24,21,-114]^[19,-7,79]))^[4,20,241]))))^(!((!((!(([30,-1,474]^([14,17,155]^[-31,-6,-153]))|[-15,-15,108]))|(([-26,-11,421]&[-15,-3,-224])&[14,-3,458])))^[9,20,-404])))^(!((!((!(([14,-6,-464]^[-11,8,...

output:

50320.052334201624156

result:

wrong answer 1st numbers differ - expected: '47063.3348524', found: '50320.0523342', error = '0.0691986'