QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#799105 | #7862. Land Trade | 口嗨战神 (Binyang Jiang, Dayu Wang, Hejun Dong) | WA | 1ms | 4104kb | C++17 | 5.3kb | 2024-12-04 22:12:59 | 2024-12-04 22:12:59 |
Judging History
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'