QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #288963 | #7862. Land Trade | ucup-team2230# | WA | 1ms | 4016kb | C++14 | 13.5kb | 2023-12-23 14:30:02 | 2023-12-23 14:30:03 |
Judging History
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();
}
详细
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'