QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#289376#7862. Land Tradeucup-team180#TL 1ms4116kbC++179.3kb2023-12-23 17:21:512023-12-23 17:21:51

Judging History

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

  • [2023-12-23 17:21:51]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4116kb
  • [2023-12-23 17:21:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
struct frac{
  long long num, den;
  frac(){
  }
  frac(long long num_, long long den_ = 1){
    num = num_;
    den = den_;
    if (den < 0){
      num *= -1;
      den *= -1;
    }
  }
  bool operator ==(frac x){
    return num * x.den == x.num * den;
  }
  bool operator <(frac x){
    return num * x.den < x.num * den;
  }
  bool operator <=(frac x){
    return num * x.den <= x.num * den;
  }
  frac operator -(frac x){
    return frac(num * x.den - x.num * den, den * x.den);
  }
  double value(){
    return (double) num / den;
  }
};
struct point{
  frac x, y;
  point(){
  }
  point(frac x, frac y): x(x), y(y){
  }
  bool operator ==(point P){
    return x == P.x && y == P.y;
  }
  bool operator <(point P){
    return x < P.x || x == P.x && y < P.y;
  }
};
struct line{
  long long a, b, c;
  line(long long a, long long b, long long c): a(a), b(b), c(c){
  }
};
bool is_parallel(line L1, line L2){
  return L1.a * L2.b - L1.b * L2.a == 0;
}
point line_intersection(line L1, line L2){
  long long det = L1.a * L2.b - L1.b * L2.a;
  long long x = (-L1.c) * L2.b - L1.b * (-L2.c);
  long long y = L1.a * (-L2.c) - (-L1.c) * L2.a;
  return point(frac(x, det), frac(y, det));
}
int main(){
  cout << fixed << setprecision(20);
  int xmin, xmax, ymin, ymax;
  cin >> xmin >> xmax >> ymin >> ymax;
  string S;
  cin >> S;
  int V = 1;
  vector<string> T(V);
  vector<vector<int>> c(V);
  vector<line> L;
  L.push_back(line(1, 0, -xmin));
  L.push_back(line(-1, 0, xmax));
  L.push_back(line(0, 1, -ymin));
  L.push_back(line(0, -1, ymax));
  int p = 0;
  auto add_vertex = [&](){
    T.push_back("");
    c.push_back(vector<int>(0));
    V++;
  };
  auto number = [&]() -> int {
    int ans = 0;
    bool neg = false;
    if (S[p] == '-'){
      neg = true;
      p++;
    }
    while (isdigit(S[p]) != 0){
      ans = ans * 10 + (S[p] - '0');
      p++;
    }
    if (neg){
      ans *= -1;
    }
    return ans;
  };
  auto dfs = [&](auto dfs, int v) -> void {
    if (S[p] == '['){
      T[v] = "L" + to_string(L.size());
      p++;
      long long a = number();
      p++;
      long long b = number();
      p++;
      long long c = number();
      p++;
      L.push_back(line(a, b, c));
    } else {
      p++;
      if (S[p] == '!'){
        T[v] = "!";
        p++;
        c[v].push_back(V);
        add_vertex();
        dfs(dfs, V - 1);
      } else {
        c[v].push_back(V);
        add_vertex();
        dfs(dfs, V - 1);
        T[v] = S[p];
        p++;
        c[v].push_back(V);
        add_vertex();
        dfs(dfs, V - 1);
      }
      p++;
    }
  };
  dfs(dfs, 0);
  int N = L.size();
  vector<point> P;
  for (int i = 0; i < N; i++){
    for (int j = i + 1; j < N; j++){
      if (!is_parallel(L[i], L[j])){
        point T = line_intersection(L[i], L[j]);
        if (frac(xmin) <= T.x && T.x <= frac(xmax) && frac(ymin) <= T.y && T.y <= frac(ymax)){
          P.push_back(T);
        }
      }
    }
  }
  sort(P.begin(), P.end());
  P.erase(unique(P.begin(), P.end()), P.end());
  int M = P.size();
  vector<frac> X;
  for (int i = 0; i < M; i++){
    X.push_back(P[i].x);
  }
  X.erase(unique(X.begin(), X.end()), X.end());
  int Xcnt = X.size();
  vector<int> left(N, Xcnt), right(N, 0);
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      if (!is_parallel(L[i], L[j])){
        point T = line_intersection(L[i], L[j]);
        if (frac(xmin) <= T.x && T.x <= frac(xmax) && frac(ymin) <= T.y && T.y <= frac(ymax)){
          int idx = lower_bound(X.begin(), X.end(), T.x) - X.begin();
          left[i] = min(left[i], idx);
          right[i] = max(right[i], idx);
        }
      }
    }
  }
  vector<vector<frac>> Y(Xcnt);
  for (int i = 0; i < N; i++){
    if (L[i].b != 0){
      for (int j = left[i]; j <= right[i]; j++){
        Y[j].push_back(frac(-L[i].c * X[j].den - L[i].a * X[j].num, L[i].b * X[j].den));
      }
    }
  }
  for (int i = 0; i < Xcnt; i++){
    sort(Y[i].begin(), Y[i].end());
    Y[i].erase(unique(Y[i].begin(), Y[i].end()), Y[i].end());
  }
  vector<vector<int>> pos(N, vector<int>(Xcnt, -1));
  for (int i = 0; i < N; i++){
    if (L[i].b != 0){
      for (int j = left[i]; j <= right[i]; j++){
        frac y(-L[i].c * X[j].den - L[i].a * X[j].num, L[i].b * X[j].den);
        pos[i][j] = lower_bound(Y[j].begin(), Y[j].end(), y) - Y[j].begin();
      }
    }
  }
  vector<vector<pair<int, int>>> E(Xcnt - 1);
  for (int i = 0; i < N; i++){
    if (L[i].b != 0){
      for (int j = left[i]; j < right[i]; j++){
        E[j].push_back(make_pair(pos[i][j], pos[i][j + 1]));
      }
    }
  }
  for (int i = 0; i < Xcnt - 1; i++){
    sort(E[i].begin(), E[i].end());
    E[i].erase(unique(E[i].begin(), E[i].end()), E[i].end());
  }
  vector<vector<vector<int>>> idx_E(Xcnt - 1);
  for (int i = 0; i < Xcnt - 1; i++){
    idx_E[i].resize(E[i].size());
  }
  for (int i = 0; i < N; i++){
    if (L[i].b != 0){
      for (int j = left[i]; j < right[i]; j++){
        int p = lower_bound(E[j].begin(), E[j].end(), make_pair(pos[i][j], pos[i][j + 1])) - E[j].begin();
        idx_E[j][p].push_back(i);
      }
    }
  }
  vector<vector<int>> idx_V(Xcnt - 2);
  for (int i = 0; i < N; i++){
    if (L[i].b == 0){
      frac x(-L[i].c, L[i].a);
      if (frac(xmin) < x && x < frac(xmax)){
        int idx = lower_bound(X.begin(), X.end(), x) - X.begin();
        idx_V[idx - 1].push_back(i);
      }
    }
  }
  vector<int> sum(Xcnt);
  sum[0] = 0;
  for (int i = 0; i < Xcnt - 1; i++){
    sum[i + 1] = sum[i] + E[i].size() - 1;
  }
  int V2 = sum[Xcnt - 1];
  vector<double> area(V2, 0);
  for (int i = 0; i < Xcnt - 1; i++){
    for (int j = 0; j < E[i].size() - 1; j++){
      double dl = (Y[i][E[i][j + 1].first] - Y[i][E[i][j].first]).value();
      double dr = (Y[i + 1][E[i][j + 1].second] - Y[i + 1][E[i][j].second]).value();
      double h = (X[i + 1] - X[i]).value();
      area[sum[i] + j] = (dl + dr) * h / 2;
    }
  }
  vector<vector<int>> idx_L(Xcnt - 1), idx_R(Xcnt - 1);
  for (int i = 0; i < Xcnt - 1; i++){
    idx_L[i].resize(Y[i].size() - 1);
    idx_R[i].resize(Y[i + 1].size() - 1);
    int Ecnt = E[i].size();
    for (int j = 0; j < Ecnt - 1; j++){
      for (int k = E[i][j].first; k < E[i][j + 1].first; k++){
        idx_L[i][k] = sum[i] + j;
      }
      for (int k = E[i][j].second; k < E[i][j + 1].second; k++){
        idx_R[i][k] = sum[i] + j;
      }
    }
  }
  vector<vector<pair<int, vector<int>>>> E2(V2);
  for (int i = 0; i < Xcnt - 1; i++){
    for (int j = 0; j < E[i].size() - 2; j++){
      E2[sum[i] + j].push_back(make_pair(sum[i] + j + 1, idx_E[i][j + 1]));
      E2[sum[i] + j + 1].push_back(make_pair(sum[i] + j, idx_E[i][j + 1]));
    }
  }
  for (int i = 1; i < Xcnt - 1; i++){
    for (int j = 0; j < Y[i].size() - 1; j++){
      E2[idx_R[i - 1][j]].push_back(make_pair(idx_L[i][j], idx_V[i - 1]));
      E2[idx_L[i][j]].push_back(make_pair(idx_R[i - 1][j], idx_V[i - 1]));
    }
  }
  vector<int> cc(V2, -1);
  int cc_cnt = 0;
  vector<bool> head(V2, false);
  for (int i = 0; i < V2; i++){
    if (cc[i] == -1){
      cc[i] = cc_cnt;
      head[i] = true;
      queue<int> Q;
      Q.push(i);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        for (auto& P : E2[v]){
          if (P.second.empty()){
            int w = P.first;
            if (cc[w] == -1){
              cc[w] = cc[v];
              Q.push(w);
            }
          }
        }
      }
      cc_cnt++;
    }
  }
  vector<bool> curr_in(N, false);
  for (int i = 0; i < 4; i++){
    curr_in[i] = true;
  }
  for (int i = 4; i < N; i++){
    if (L[i].a * xmin + L[i].b * ymin + L[i].c > 0){
      curr_in[i] = true;
    } else if (L[i].a * xmin + L[i].b * ymin + L[i].c  == 0){
      if (L[i].a > 0){
        curr_in[i] = true;
      } else if (L[i].a == 0){
        if (L[i].b > 0){
          curr_in[i] = true;
        }
      }
    }
  }
  vector<vector<bool>> cc_in(cc_cnt);
  vector<bool> used(V2, false);
  auto dfs2 = [&](auto dfs2, int v) -> void {
    if (head[v]){
      cc_in[cc[v]] = curr_in;
    }
    for (auto& e : E2[v]){
      int w = e.first;
      if (!used[w]){
        used[w] = true;
        for (int idx : e.second){
          curr_in[idx] = !curr_in[idx];
        }
        dfs2(dfs2, w);
        for (int idx : e.second){
          curr_in[idx] = !curr_in[idx];
        }
      }
    }
  };
  dfs2(dfs2, 0);
  vector<double> area_sum(cc_cnt, 0);
  for (int i = 0; i < V2; i++){
    area_sum[cc[i]] += area[i];
  }
  double ans = 0;
  for (int i = 0; i < cc_cnt; i++){
    auto dfs3 = [&](auto dfs3, int v) -> bool {
      if (T[v][0] == 'L'){
        return cc_in[i][stoi(T[v].substr(1))];
      }
      if (T[v] == "!"){
        return !dfs3(dfs3, c[v][0]);
      }
      if (T[v] == "&"){
        return dfs3(dfs3, c[v][0]) && dfs3(dfs3, c[v][1]);
      }
      if (T[v] == "|"){
        return dfs3(dfs3, c[v][0]) || dfs3(dfs3, c[v][1]);
      }
      if (T[v] == "^"){
        return dfs3(dfs3, c[v][0]) ^ dfs3(dfs3, c[v][1]);
      }
    };
    if (dfs3(dfs3, 0)){
      ans += area_sum[i];
    }
  }
  cout << ans << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

0.50000000000000000000

result:

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

Test #2:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

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

output:

70.45169340463458240720

result:

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

Test #3:

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

input:

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

output:

0.00000000000000000000

result:

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

Test #4:

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

input:

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

output:

0.00050000000000000001

result:

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

Test #5:

score: 0
Accepted
time: 1ms
memory: 4116kb

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:

47063.33485244146868353710

result:

ok found '47063.3348524', expected '47063.3348524', error '0.0000000'

Test #6:

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

input:

767 957 738 941
((!(((!([3,-3,507]^[-30,-10,425]))^[-6,7,643])^((!((!([-11,0,450]^[21,17,-65]))&(!([17,0,64]^[-11,0,804]))))|[-31,10,-687])))&((!(([-34,12,-527]^(!([17,-14,-219]^(!([13,-27,-105]^(!([18,-47,-110]&(!([-9,-20,-455]^[-18,26,-228])))))))))^([-4,0,144]^[10,1,396])))^((!((!([35,0,-221]&[-5...

output:

36999.05865566321881487966

result:

ok found '36999.0586557', expected '36999.0586557', error '0.0000000'

Test #7:

score: -100
Time Limit Exceeded

input:

-513 213 -733 114
(!((!((!((((!([2,16,-57]|[15,40,-272]))^((!(([0,26,315]|[5,-4,-336])^(!([-12,2,218]&([17,-16,-730]&[-7,3,-263])))))^[18,-7,29]))^[5,30,-126])^((!(((!((([8,9,406]^(!([-26,6,63]^[-38,-25,108])))^(([-9,20,220]^(!([-2,-27,213]^[29,16,-269])))|[-12,-4,-586]))^([30,0,-443]|(!((!([-17,0,3...

output:


result: