QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799105#7862. Land Trade口嗨战神 (Binyang Jiang, Dayu Wang, Hejun Dong)WA 1ms4104kbC++175.3kb2024-12-04 22:12:592024-12-04 22:12:59

Judging History

This is the latest submission verdict.

  • [2024-12-04 22:12:59]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4104kb
  • [2024-12-04 22:12:59]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

using ll = long long;
using db = double;

const int mod = 1e9 + 7;
int add(int x, int y) {
    x += y;
    return x >= mod ? x - mod : x;
}
void addto(int& x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}

int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = mul(ans, a);
        a = mul(a, a);
        b >>= 1;
    }
    return ans;
}

const int maxn = 1111;

const db eps = 1e-9;
int sgn(db x) {
    if (x > eps) return 1;
    if (x < -eps) return -1;
    return 0;
}

struct vec {
    db x, y;
    vec(db _x = 0, db _y = 0) : x(_x), y(_y) {}
    vec operator+(vec b) {
        return vec(x + b.x, y + b.y);
    }
    vec operator-(vec b) {
        return vec(x - b.x, y - b.y);
    }
    vec operator*(db b) {
        return vec(x * b, y * b);
    }
    db operator*(vec b) {
        return x * b.y - y * b.x;
    }
};
db cross(vec a, vec b, vec c) {
    return (b - a) * (c - a);
}
vec inter(vec p1, vec p2, vec q1, vec q2) {
    db s1 = cross(p1, q1, p2);
    db s2 = cross(p1, p2, q2);
    db t1 = s1 / (s1 + s2);
    db t2 = s2 / (s1 + s2);
    return  q2*t1  +  q1*t2;
}

vector<vector<vec>> split(vector<vec> p, vec p1, vec p2) {
    int havepos1 = -1, haveneg1 = -1;
    for (int i=0;i<p.size();i++) {
        int tmp = sgn(cross(p1, p2, p[i]));
        if (tmp == -1) haveneg1 = i;
        if (tmp == 1) havepos1 = i;
    }
    if (havepos1==-1 || haveneg1==-1) return {p};
    auto ne=[&](int i){
        return i+1==p.size()?0:i+1;
    };
    auto pre=[&](int i){
        return i==0?(int)p.size()-1:i-1;
    };
    while(sgn(cross(p1, p2, p[ne(havepos1)]))==1)havepos1=ne(havepos1);
    while(sgn(cross(p1, p2, p[ne(haveneg1)]))==-1)haveneg1=ne(haveneg1);
    auto q1=inter(p[haveneg1], p[ne(haveneg1)], p1, p2);
    auto q2=inter(p[havepos1], p[ne(havepos1)], p1, p2);
    vector<vec> ans1, ans2;
    ans1.push_back(q2);
    ans1.push_back(q1);
    while(sgn(cross(p1,p2,p[haveneg1]))==-1)ans1.push_back(p[haveneg1]),haveneg1=pre(haveneg1);
    ans2.push_back(q1);
    ans2.push_back(q2);
    while(sgn(cross(p1,p2,p[havepos1]))==1)ans2.push_back(p[havepos1]),havepos1=pre(havepos1);
    reverse(ans1.begin(), ans1.end())  ;
    reverse(ans2.begin(), ans2.end());
    return {ans1, ans2};
}

vector<int>tr[maxn];
string ty[maxn];
int id[maxn];
int A[maxn],B[maxn],C[maxn];
int linecnt;
int cnt;
int curpos=0;
string s;
int res[maxn];
int parse(){
    if(s[curpos]=='-'||isdigit(s[curpos])){
        int sym=1;
        if(s[curpos]=='-')sym=-1,curpos++;
        int x=0;
        while(isdigit(s[curpos]))x=x*10+s[curpos++]-'0';
        return sym*x;
    }
    int cur=++cnt;
    if(s[curpos]=='['){
        ++curpos;
        ++linecnt;
        id[cur]=linecnt;
        ty[cur]="atomic";
        A[linecnt]=parse();
        ++curpos;
        B[linecnt]=parse();
        ++curpos;
        C[linecnt]=parse();
        ++curpos;
        return cur;
    }
    ++curpos;
    if(s[curpos]=='!'){
        ++curpos;
        ty[cur]="not";
        tr[cur].push_back(parse());
        ++curpos;
        return cur;
    }
    tr[cur].push_back(parse());
    if(s[curpos]=='&')ty[cur]="and";
    if(s[curpos]=='^')ty[cur]="xor";
    if(s[curpos]=='|')ty[cur]="or";
    curpos++;
    tr[cur].push_back(parse());
    ++curpos;
    return cur;
    
}
vec cent(vector<vec>p){
    db a=0;
    vec b;
    for(int i=1;i+1<p.size();i++){
        db s=cross(p[0],p[i],p[i+1])/2;
        vec cen=(p[0]+p[i]+p[i+1])*(1./3);
        a+=s;
        b=b+cen*s;
    }
    return b*(1./a);
}
db S(vector<vec>p){
    db a=0;
    for(int i=1;i+1<p.size();i++){
        db s=cross(p[0],p[i],p[i+1])/2;
        a+=s;
    }
    return a;
}

int getres(int i){
    if(ty[i]=="atomic")return res[id[i]];
    if(ty[i]=="not")return !getres(tr[i][0]);
    if(ty[i]=="and")return getres(tr[i][0])&&getres(tr[i][1]);
    if(ty[i]=="or")return getres(tr[i][0])||getres(tr[i][1]);
    return getres(tr[i][0])^getres(tr[i][1]);
}
void solve() {
    db xmi,xma,ymi,yma;
    cin>>xmi>>xma>>ymi>>yma;;
    vector<vector<vec>>p={{vec(xmi,ymi),vec(xma,ymi),vec(xma,yma),vec(xmi,yma)}};
    cin>>s;
    curpos=0;
    int rt=parse();
    for(int i=1;i<=linecnt;i++){
        vec p1,p2;
        if(B[i]==0){
            p1=vec(-1.*C[i]/A[i],0);
            p1=vec(-1.*C[i]/A[i],100);
        }
        else{
            p1=vec(0,-1.*C[i]/B[i]);
            p2=vec(10,-1.*C[i]/B[i]-10.*A[i]/B[i]);
        }
        vector<vector<vec>> np;
        for(auto poly:p){
            for(auto q:split(poly,p1,p2)){
                np.push_back(q);
            }
        }
        p=np;
    }
    db ans=0;
    for(auto q:p){
        auto cen=cent(q);
        for(int i=1;i<=linecnt;i++){
            if(A[i]*cen.x+B[i]*cen.y+C[i]>0){
                res[i]=1;
            }
            else res[i]=0;
        }
        if(getres(rt))ans+=S(q);
    }
    cout<<fixed<<setprecision(20)<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // 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: 100
Accepted
time: 1ms
memory: 3932kb

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: 0ms
memory: 3880kb

input:

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

output:

70.45169340463456819634

result:

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

Test #3:

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

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: 4104kb

input:

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

output:

0.00050000000400718392

result:

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

Test #5:

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

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:

47508.49848456161998910829

result:

wrong answer 1st numbers differ - expected: '47063.3348524', found: '47508.4984846', error = '0.0094588'