QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#289504 | #7862. Land Trade | ucup-team266 | WA | 425ms | 43440kb | C++20 | 5.0kb | 2023-12-23 18:01:30 | 2023-12-23 18:01:30 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
#define x first
#define y second
#define x1 x114514
#define x2 x1919810
#define y1 y114514
#define y2 y1919810
#define index _index
typedef long double ldb;
void die(string S){puts(S.c_str());exit(0);}
const ldb eps=1e-16;
struct line
{
ldb A,B,C;
line(ldb _A,ldb _B,ldb _C):A(_A),B(_B),C(_C){}
line(){}
}L[1010];
int x1,x2,y1,y2;
string s;
struct formula
{
formula *a,*b;
int op;
};
const pair<ldb,ldb> error=mp(20210109,20210448);
pair<ldb,ldb> its(line a,line b)
{
ldb B=a.B*b.A-b.B*a.A,C=a.C*b.A-b.C*a.A;
ldb y=-C/B;
ldb x=(-a.C-a.B*y)/a.A;
if(fabs(B)<eps) return error;
if(fabs(a.A)<eps) x=(-b.C-b.B*y)/b.A;
return mp(x,y);
}
int tot;
formula *get(int l,int r)
{
int c=0,p=-1;
for(int i=l;i<=r;i++)
{
if(s[i]=='(')
c++;
if(s[i]==')')
c--;
if(s[i]=='!'||s[i]=='&'||s[i]=='|'||s[i]=='^') if(!c)
p=i;
}
if(p==-1)
{
if(s[l]=='(')
return get(l+1,r);
formula *ret=new formula;
ret->op=++tot;
vector<int> vec;
int x=0,f=0;
for(int i=l;i<=r;i++)
{
if(isdigit(s[i]))
{
x=x*10+(s[i]^48);
if(!f) f=1;
}
else if(s[i]=='-')
f=-1;
else if(f)
{
vec.pb(x*f);
x=0;
f=0;
}
}
assert(sz(vec)==3);
L[tot]=line(vec[0],vec[1],vec[2]);
return ret;
}
else
{
if(s[p]=='!')
{
formula *ret=new formula;
ret->op=-4;
ret->a=get(l+1,r);
return ret;
}
formula *ret=new formula;
ret->op=(s[p]=='&'?-1:(s[p]=='|'?-2:-3));
ret->a=get(l,p-1);
ret->b=get(p+1,r);
return ret;
}
}
vector<pair<pair<ldb,ldb>,pii>> vec;
int lst[1010];
vector<pair<ldb,int>> G[100100];
ldb calc(int a,int b)
{
return atan2(vec[b].x.y-vec[a].x.y,vec[b].x.x-vec[a].x.x);
}
map<int,int> index[100100];
map<pii,bool> vis;
bool status[100100];
pair<ldb,ldb> ctr(pair<ldb,ldb> a,pair<ldb,ldb> b,pair<ldb,ldb> c)
{
return mp((a.x+b.x+c.x)/3,(a.y+b.y+c.y)/3);
}
bool calc(formula *F)
{
if(F->op>0) return status[F->op];
if(F->op==-4) return !calc(F->a);
bool a=calc(F->a),b=calc(F->b);
if(F->op==-1) return a&b;
if(F->op==-2) return a|b;
return a^b;
}
map<pair<ldb,ldb>,vector<int>> belong;
const bool operator ==(const pair<ldb,ldb> &a,const pair<ldb,ldb> &b)
{
return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>x1>>x2>>y1>>y2;
cin>>s;
formula *F=get(0,sz(s)-1);
L[tot+1]=line(1,0,-x1);
L[tot+2]=line(0,-1,y2);
L[tot+3]=line(-1,0,x2);
L[tot+4]=line(0,1,-y1);
int cnt=0;
for(int i=1;i<=tot+4;i++)
for(int j=i+1;j<=tot+4;j++)
{
pair<ldb,ldb> p=its(L[i],L[j]);
if(p==error) continue;
if(p.x<x1-eps||p.x>x2+eps||p.y<y1-eps||p.y>y2+eps)
continue;
belong[p].pb(i);
belong[p].pb(j);
vec.pb(p,mp(0,0));
}
srt(vec);
uni(vec);
int n=sz(vec);
memset(lst,-1,sizeof(lst));
vector<int> ban;
for(int i=0;i<n;i++)
{
auto pr=vec[i];
bool flag=0;
srt(belong[pr.first]);
uni(belong[pr.first]);
for(auto a:belong[pr.first])
{
if(a>tot) flag=1;
if(lst[a]!=-1)
{
G[lst[a]].pb(calc(lst[a],i),i);
G[i].pb(calc(i,lst[a]),lst[a]);
}
lst[a]=i;
}
if(flag)
ban.pb(i);
}
for(int i=0;i<n;i++)
{
srt(G[i]);
for(int j=0;j<sz(G[i]);j++)
index[i][G[i][j].second]=j;
}
srt(ban);
vector<array<int,3>> pool;
for(int i=0;i<n;i++)
for(auto pr:G[i])
if(!vis[mp(i,pr.second)])
{
vector<int> cvh;
int cura=i,curb=pr.second;
while(!vis[mp(cura,curb)])
{
vis[mp(cura,curb)]=1;
cvh.pb(curb);
int p=index[curb][cura];
p=(p+1)%sz(G[curb]);
cura=curb;
curb=G[cura][p].second;
}
if(sz(cvh)<3) continue;
vector<int> tmp=cvh;
srt(tmp);
if(tmp==ban)
{
ban.clear();
continue;
}
for(int i=2;i<sz(cvh);i++)
pool.push_back({cvh[0],cvh[i-1],cvh[i]});
}
ldb ans=0;
for(auto arr:pool)
{
int a=arr[0],b=arr[1],c=arr[2];
pair<ldb,ldb> center=ctr(vec[a].first,vec[b].first,vec[c].first);
memset(status,0,sizeof(status));
for(int i=1;i<=tot;i++)
if(L[i].A*center.x+L[i].B*center.y+L[i].C>-eps)
status[i]=1;
if(calc(F))
{
ldb S=0;
ldb ax=vec[a].x.x-vec[c].x.x,ay=vec[a].x.y-vec[c].x.y,bx=vec[b].x.x-vec[c].x.x,by=vec[b].x.y-vec[c].x.y;
S=fabs(ax*by-ay*bx)/2;
ans+=S;
}
}
printf("%.20Lf\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 10984kb
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: 3ms
memory: 10996kb
input:
-5 10 -10 5 ((!([1,2,-3]&[10,3,-2]))^([-2,3,1]|[5,-2,7]))
output:
70.45169340463458110269
result:
ok found '70.4516934', expected '70.4516934', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 10984kb
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: 10932kb
input:
0 1000 0 1000 (([1,-1,0]&[-1000,999,999])&([1,0,-998]&[0,1,-998]))
output:
0.00050000000000000044
result:
ok found '0.0005000', expected '0.0005000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 10956kb
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.33485244147654213975
result:
ok found '47063.3348524', expected '47063.3348524', error '0.0000000'
Test #6:
score: 0
Accepted
time: 3ms
memory: 10832kb
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.05865566322222193207
result:
ok found '36999.0586557', expected '36999.0586557', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 425ms
memory: 43440kb
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:
2227725.03521885721670514613
result:
wrong answer 1st numbers differ - expected: '295728.6081036', found: '2227725.0352189', error = '6.5330048'