QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288963#7862. Land Tradeucup-team2230#WA 1ms4016kbC++1413.5kb2023-12-23 14:30:022023-12-23 14:30:03

Judging History

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

  • [2023-12-23 14:30:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4016kb
  • [2023-12-23 14:30:02]
  • 提交

answer

//Let's join Kaede Takagaki Fan Club !!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
//#include <unordered_map>
//#include <unordered_set>
#include <cassert>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <atcoder/convolution>
//#include <atcoder/lazysegtree>
//#include <atcoder/maxflow>
//#include <atcoder/mincostflow>
//#include <atcoder/segtree>
//#include <atcoder/string>
using namespace std;
//using namespace atcoder;
#define int long long
//#define L __int128
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define a first
#define b second
#define fi first
#define sc second
#define rng(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,x) for(int i=0;i<x;i++)
#define gnr(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define per(i,b) gnr(i,0,b)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
#define si(x) (int)(x.size())
#define pcnt(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()

#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
 
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
 
template<class t> using vc=vector<t>;
 
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.fi<<","<<p.sc<<"}";
}
 
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}
 
 //https://codeforces.com/blog/entry/62393
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
	//don't make x negative!
	size_t operator()(pair<int,int> x)const{
		return operator()(uint64_t(x.first)<<32|x.second);
	}
};
//unordered_set -> dtype, null_type
//unordered_map -> dtype(key), dtype(value)
using namespace __gnu_pbds;
template<class t,class u>
using hash_table=gp_hash_table<t,u,custom_hash>;

template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 998244353;
//const ll mod = 1000000007;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

struct mint{
	ll v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(ll vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint &operator+=(const mint&rhs){return s(v+rhs.v);}
	mint &operator-=(const mint&rhs){return s(v+mod-rhs.v);}
	mint &operator*=(const mint&rhs){v=ll(v)*rhs.v%mod;return *this;}
	mint &operator/=(const mint&rhs){return *this*=rhs.inv();}
	mint operator+(const mint&rhs)const{return mint(*this)+=rhs;}
	mint operator-(const mint&rhs)const{return mint(*this)-=rhs;}
	mint operator*(const mint&rhs)const{return mint(*this)*=rhs;}
	mint operator/(const mint&rhs)const{return mint(*this)/=rhs;}
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
	friend mint operator+(ll x,const mint&y){
		return mint(x)+y;
	}
	friend mint operator-(ll x,const mint&y){
		return mint(x)-y;
	}
	friend mint operator*(ll x,const mint&y){
		return mint(x)*y;
	}
	friend mint operator/(ll x,const mint&y){
		return mint(x)/y;
	}
	friend ostream& operator<<(ostream&os,const mint&m){
		return os<<m.v;
	}
	friend istream& operator>>(istream&is,mint&m){
		ll x;is>>x;
		m=mint(x);
		return is;
	}
	bool operator<(const mint&r)const{return v<r.v;}
	bool operator==(const mint&r)const{return v==r.v;}
	bool operator!=(const mint&r)const{return v!=r.v;}
	explicit operator bool()const{
		return v;
	}
};
ll modpow(ll x,ll n,ll _md=mod){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%_md;
		x=x*x%_md;
		n>>=1;
	}
	return res;
}
#define _sz 1
mint F[_sz],R[_sz];
void make(){
	F[0] = 1;
	for(int i=1;i<_sz;i++) F[i] = F[i-1] * i;
	R[_sz-1] = F[_sz-1].pow(mod-2);
	for(int i=_sz-2;i>=0;i--) R[i] = R[i+1] * (i+1);
}
mint C(int a,int b){
	if(b < 0 || a < b) return mint();
	return F[a]*R[b]*R[a-b];
}
using ld=long double;
using vi=vc<int>;
using ull=unsigned long long;
/*int dst(P p, P q){
	return (p.a-q.a)*(p.a-q.a)+(p.b-q.b)*(p.b-q.b);
}*/
/*template<class t>
void add_inplace(t &a, t b){
	if(a.size() < b.size()) swap(a, b);
	for(int i=0;i<si(b);i++){
		a[i] += b[i];
		if(a[i] < 0) a[i] += mod;
		if(a[i] >= mod) a[i] -= mod;
	}
	return ;
}*/
template<class t>
void ov(const vc<t>&a){
	if(a.empty()) return;
	rep(i, si(a)) cout << a[i] << (i+1==si(a)?'\n':' ');
}
//o(ans?"Yes":"No");
#define double long double
typedef complex<double> pt;
typedef pair<pt,pt> L;
typedef vector<P> poly;
const double EPS = 1e-12;
#define x real()
#define y imag()
bool eq(double a,double b){
  return (-EPS < a-b && a-b < EPS);
}
double dot(pt a,pt b){
	return (conj(a)*b).x;
}
double cross(pt a,pt b){
	return (conj(a)*b).y;
}
int ccw(pt a,pt b,pt c){
	b -= a; c -= a;
	if(cross(b,c) > EPS) return 1; // counter clockwise
	if(cross(b,c) < -EPS) return -1; // clockwise
	if(dot(b,c) < -EPS) return 2; //c-a-b
	if(norm(b) < norm(c)) return -2; //a-b-c
	return 0; //a-c-b
}
bool cmp(const pt& a,const pt& b){
	if(-EPS < a.x-b.x && a.x-b.x < EPS) return a.y < b.y;
	else return a.x < b.x;
}
vector<pt>convex_hull(vector<pt>ps)
{
	sort(ps.begin(),ps.end(),cmp);
	int k=0,n = ps.size();
	vector<pt>qs(n*2);
	for(int i=0;i<n;i++)
	{
		while(k>1 && ccw(qs[k-2],qs[k-1],ps[i]) == -1) k--;
		qs[k++] = ps[i];
	}
	for(int i=n-2,t=k;i>=0;i--)
	{
		while(k>t && ccw(qs[k-2],qs[k-1],ps[i]) == -1) k--;
		qs[k++] = ps[i];
	}
	qs.resize(k-1);
	return qs;
}
//平行?
bool is_par(pt a,pt b,pt c,pt d){
    b -= a; d -= c;
	if(abs(b.y*d.x - b.x*d.y) < EPS){
		return 1;
	}
	return 0;
}

//直線同士
pt crossPoint(pt a,pt b,pt c,pt d){
	double A = cross(b-a,d-c);
	double B = cross(b-a,b-c);
	if( fabs(A) < EPS && fabs(B) < EPS ) return c;
	else if(fabs(A) >= EPS ) return c+B/A*(d-c);
	else return pt(1e9,1e9);
}
//線分上に点pがあるか
bool on_segment(pair<pt,pt> a,pt p){
	bool ret = eq(abs(a.a-p), 0);
	ret |= eq(abs(a.b-p), 0);
	//整数なら誤差無し↓
	ret |= ccw(a.a, p, a.b) == -2;
	return ret;
	//eq(abs(a.first-a.second)-abs(a.first-p)-abs(a.second-p),0);
}
//円 & 円 の交点
vector<pt> CCintersect (pair<pt,double> c, pair<pt,double> d) {
    vector<pt> ret;
    double dist = abs(c.first - d.first);
    double cr = c.second;
    double dr = d.second;
     
    if (dist > cr + dr) return ret;
    if (dist < abs(cr - dr)) return ret;
     
    double s = (cr + dr + dist) / 2.;
    double area = sqrt(s * (s - cr) * (s - dr) * (s - dist));
    double h = 2 * area / dist;
     
    pt v = d.first - c.first; v /= abs(v);
    pt m = c.first + sqrt(cr * cr - h * h) * v;
    pt n = v * pt(0, 1);
     
    ret.push_back(m + n * h);
    ret.push_back(m - n * h);
    return ret;
}
//線分a-b とc の距離
double dist_lp(pt a,pt b,pt c){
	if(dot(a-b,c-b) <= 0.0) return abs(c-b);
	if(dot(b-a,c-a) <= 0.0) return abs(c-a);
	return abs(cross(b-a,c-a)) / abs(b-a);
}
//線分が交わる?
bool intersect(pt a,pt b,pt c,pt d){
	return (ccw(a,b,c)*ccw(a,b,d) <= 0 && ccw(c,d,a)*ccw(c,d,b) <= 0);
}
//線分a-b と 線分c-d の距離
double min_dist_ll(pt a,pt b,pt c,pt d){
    if(intersect(a,b,c,d) == true) return 0.0;
    double ret = 1e18;
    ret = min(ret,dist_lp(a,b,c));
    ret = min(ret,dist_lp(a,b,d));
    ret = min(ret,dist_lp(c,d,a));
    ret = min(ret,dist_lp(c,d,b));
    return ret;
}
bool contain_point(vector<pt>ps,pt p){
	double sum = 0;
	//arg no sum wo keisan
	for(int i=0;i<ps.size();i++){
		if(on_segment(mp(ps[i],ps[ (i+1)%ps.size() ]),p)) return 1;
		sum += arg( (ps[ (i+1)%ps.size() ]-p) / (ps[i]-p) );
	}
	return (abs(sum) > 1);
}
bool LCMP(const pt& a,const pt& b){
	if(eq(a.x,b.x)) return a.y < b.y;
	else return a.x < b.x;
}
bool contain_segment(vector<pt>ps,pt p,pt q){
        vector<pt> qs;
        qs.pb(p); qs.pb(q);
    	for(int i=0;i<ps.size();i++){
    		//on-segment
    		if(ccw(p,q,ps[i]) == 0) qs.pb(ps[i]);
    	}
        for(int i=0;i<ps.size();i++){
        	pt r = crossPoint(p,q,ps[i],ps[(i+1)%ps.size()]);
        	if(r.x > 1e8) continue;
        	if(ccw(p,q,r) == 0) qs.pb(r);
        }
        sort(qs.begin(),qs.end(),LCMP);
        for(int i=1;i<qs.size();i++){
            pt r = (qs[i] + qs[i-1]) / (double)2.0;
            if(!contain_point(ps, r)) return 0;
        }
        return 1;
}
//G -> counter-clockwise
vector<pt> convex_cut(vector<pt> G, pair<pt,pt>l){
  vector<pt> ans;
  for(int i=0;i<(int)G.size();i++){
    pt A = G[i];
    pt B = G[(i+1)%G.size()];
    if(ccw(l.fi,l.sc,A) != -1) ans.pb(A);
    if(ccw(l.fi,l.sc,A) * ccw(l.fi,l.sc,B) < 0)
      ans.pb(crossPoint(A,B,l.fi,l.sc));
  }
  return ans;
}
int nxt,ty[1505],ch[2][1505];
ld a[1505],b[1505],c[1505];
bool dp[1505];
int pr[10005];
vc<tuple<ld,ld,ld>>ln;
string s;
void dfs(int v, int le, int ri){
	if(s[le] == '['){
		//atomic
		string str[3]={};
		int now=0;
		rng(i,le+1,ri){
			if(s[i]==',') now++;
			else str[now].pb(s[i]);
		}
		ln.eb(stoi(str[0]),stoi(str[1]),stoi(str[2]));
		ty[v] = -1;
		a[v] = stoi(str[0]), b[v] = stoi(str[1]), c[v] = stoi(str[2]);
		return;
	}
	int cnt = 0;
	while(le < ri and s[le+1] == '!'){
		cnt++; le+=2; ri--;
	}
	if(cnt){
		if(cnt&1){
			ty[v] = 0; ch[0][v] = nxt++;
		}
		dfs(nxt-1, le, ri);
	}
	else{
		int xx = pr[le+1];
		assert(s[xx+1] == '&' or s[xx+1] == '|' or s[xx+1] == '^');
		if(s[xx+1] == '&') ty[v] = 1;
		else if(s[xx+1] == '|') ty[v] = 2;
		else ty[v] = 3;
		ch[0][v] = nxt++; dfs(nxt-1, le+1, xx);
		ch[1][v] = nxt++; dfs(nxt-1, xx+2, ri-1);
	}
}
//面積
double area(vc<pt>ax){
    int n = ax.size();
	/*
	//only for convex polygons!!
	//convert to counter-clockwise
	for(int i=0;i<n;i++){
    	int f = ccw(ax[(i+0)%n], ax[(i+1)%n], ax[(i+2)%n]);
    	if(abs(f) == 1); else continue;
    	
    	if(f != 1){
    		for(int i=1;i<n;i++){
    			if(i >= n-i) break;
    			swap(ax[i], ax[n-i]);
    		}
    	}
    	break;
	}
	*/
	double ans = 0.0;
	for(int i=0;i<n;i++){
		ans += cross(ax[i], ax[(i+1)%n]);
	}
	return abs(ans) / 2.0;
}

void solve(){
	vc<pt>vec;
	ld xmn,xmx,ymn,ymx;
	cin>>xmn>>xmx>>ymn>>ymx;
	vec.eb(xmn, ymn); vec.eb(xmx, ymn);
	vec.eb(xmx, ymx); vec.eb(xmn, ymx);
	cin>>s;
	stack<int>S;
	rep(i,si(s)){
		if(s[i]=='(' or s[i]=='[') S.push(i);
		else if(s[i]==')' or s[i]==']'){
			int xx = S.top(); S.pop();
			pr[xx] = i;
			pr[i] = xx;
		}
	}
	dfs(nxt++, 0, si(s)-1);
	int sz = nxt;
	//for(auto [a,b,c]:ln)cout<<a<<" "<<b<<" "<<c<<endl;
	//o(nxt);
	vc<vc<pt>>cur{vec}, nxt;
	auto check = [](vc<pt>p){
		if(si(p) < 3) return false;
		rep(i,si(p)){
			auto a = p[i];
			auto b = p[(i+1)%si(p)];
			auto c = p[(i+2)%si(p)];
			if(ccw(a,b,c) != 1) return false;
		}
		return true;
	};
	for(auto [a,b,c]:ln){
		pair<pt,pt>pp;
		if(a == 0){
			pp.a = pt(-10000, -c/b);
			pp.b = pt(10000, -c/b);
		}
		else{
			pp.a = pt((-c+b*10000)/a, -10000);
			pp.b = pt((-c-b*10000)/a, 10000);
		}
		nxt.clear();
		for(auto p:cur){
			auto p0 = convex_cut(p, pp);
			swap(pp.a, pp.b);
			auto p1 = convex_cut(p, pp);
			//cout<<p0<<endl;
			//cout<<p1<<endl;
			bool ex = 0;
			if(check(p0)) nxt.eb(p0), ex = 1;
			if(check(p1)) nxt.eb(p1), ex = 1;
			assert(ex);
		}
		swap(cur, nxt);
	}
	ld sum_area = 0, ans = 0;
	
	for(auto p:cur){
		auto ap = area(p);
		pt g(0,0);
		for(auto xy:p) g+=xy;
		g /= (ld)(si(p));
		//o(g);assert(contain_point(p, g));
		for(int i=sz-1;i>=0;i--){
			if(ty[i] == -1){
				ld flag = a[i]*g.x + b[i]*g.y + c[i];
				if(flag >= 0) dp[i] = true;
				else dp[i] = false;
			}
			else if(ty[i] == 0){
				dp[i] = !dp[ch[0][i]];
			}
			else if(ty[i] == 1){
				dp[i] = (dp[ch[0][i]]&dp[ch[1][i]]);
			}
			else if(ty[i] == 2){
				dp[i] = (dp[ch[0][i]]|dp[ch[1][i]]);
			}
			else{
				dp[i] = (dp[ch[0][i]]^dp[ch[1][i]]);
			}
			//cout<<i<<" "<<ty[i]<<" "<<dp[i]<<" "<<g<<endl;
		}
		if(dp[0]) ans += ap;
		sum_area += ap;
	}
	//o(cur);
	cerr << sum_area << " " << (xmx-xmn)*(ymx-ymn) << endl;
	
	o(ans);
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int t; t=1;//scin >> t;
	while(t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

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

output:

70.45169340463458476642

result:

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

Test #3:

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

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: -100
Wrong Answer
time: 0ms
memory: 3980kb

input:

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

output:

0.00000000000000000000

result:

wrong answer 1st numbers differ - expected: '0.0005000', found: '0.0000000', error = '0.0005000'