QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#286885#7862. Land TradePhantomThresholdWA 233ms17228kbC++208.6kb2023-12-18 22:38:172023-12-18 22:38:18

Judging History

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

  • [2023-12-18 22:38:18]
  • 评测
  • 测评结果:WA
  • 用时:233ms
  • 内存:17228kb
  • [2023-12-18 22:38:17]
  • 提交

answer

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

int __CNT=0;

typedef long double db;
const db eps=1e-12;
const db pi=acos(-1);
int sign(db k){
	if (k>eps) return 1;
	else if (k<-eps) return -1;
	return 0;
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}// k3 在 [k1,k2] 内
struct point{
	db x,y;
	point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
	point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
	point operator * (db k1) const{return (point){x*k1,y*k1};}
	point operator / (db k1) const{return (point){x/k1,y/k1};}
	int operator == (const point &k1) const{return cmp(x,k1.x)==0&&cmp(y,k1.y)==0;}
	// 逆时针旋转
	point turn(db k1){return (point){x*cos(k1)-y*sin(k1),x*sin(k1)+y*cos(k1)};}
	point turn90(){return (point){-y,x};}
	bool operator < (const point k1) const{
		int a=cmp(y,k1.y);
		if (a==-1) return 1; else if (a==1) return 0; else return cmp(x,k1.x)==-1;
	}
	db abs(){return sqrt(x*x+y*y);}
	db abs2(){return x*x+y*y;}
	db dis(point k1){return ((*this)-k1).abs();}
	point unit(){db w=abs(); return (point){x/w,y/w};}
	/*
	void scan(){double k1,k2; scanf("%lf%lf",&k1,&k2); x=k1; y=k2;}
	void print(){printf("%.11lf %.11lf\n",x,y);}
	*/
	
	friend ostream& operator << (ostream& os,const point &P){
		os << "(" << P.x << "," << P.y << ")";
		return os;	
	}
	
	db getw(){return atan2(y,x);}
	point getdel(){
		if (sign(x)==-1||(sign(x)==0&&sign(y)==-1)) return (*this)*(-1);
		else return (*this);
	}
	int getP() const{return sign(y)==-1||(sign(y)==0&&sign(x)==-1);}
};
int inmid(point k1,point k2,point k3){
	return inmid(k1.x,k2.x,k3.x)&&inmid(k1.y,k2.y,k3.y);
}
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
db rad(point k1,point k2){return atan2(cross(k1,k2),dot(k1,k2));}
// -pi -> pi
int compareangle (point k1,point k2){
	return k1.getP()<k2.getP()||(k1.getP()==k2.getP()&&sign(cross(k1,k2))>0);
}
point proj(point k1,point k2,point q){ // q 到直线 k1,k2 的投影
	point k=k2-k1; return k1+k*(dot(q-k1,k)/k.abs2());
}
int checkLL(point k1,point k2,point k3,point k4){// 求直线 (L) 线段 (S)k1,k2 和 k3,k4 的交点
	return cmp(cross(k3-k1,k4-k1),cross(k3-k2,k4-k2))!=0;
}
point getLL(point k1,point k2,point k3,point k4){
	db w1=cross(k1-k3,k4-k3),w2=cross(k4-k3,k2-k3); return (k1*w2+k2*w1)/(w1+w2);
}

struct line{
	// p[0]->p[1]
	point p[2];
	line(point k1,point k2){p[0]=k1; p[1]=k2;}
	point& operator [] (int k){return p[k];}
	int include(point k){return sign(cross(p[1]-p[0],k-p[0]))>0;}
	point dir(){return p[1]-p[0];}
	/*
	line push(){ // 向外 ( 左手边 ) 平移 eps
		const db eps = 1e-6;
		point delta=(p[1]-p[0]).turn90().unit()*eps;
		return {p[0]-delta,p[1]-delta};
	}
	*/
	friend ostream& operator << (ostream& os,const line &L){
		os << "{" << L.p[0] << "->" << L.p[1] << "}";
		return os;	
	}
};
bool checkLL(line k1,line k2){return checkLL(k1[0],k1[1],k2[0],k2[1]);}
point getLL(line k1,line k2){return getLL(k1[0],k1[1],k2[0],k2[1]);}
int parallel(line k1,line k2){return sign(cross(k1.dir(),k2.dir()))==0;}
int sameDir(line k1,line k2){
	return parallel(k1,k2)&&sign(dot(k1.dir(),k2.dir()))==1;
}
int operator < (line k1,line k2){
	if (sameDir(k1,k2)) return k2.include(k1[0]);
	return compareangle(k1.dir(),k2.dir());
}
int checkpos(line k1,line k2,line k3){return k3.include(getLL(k1,k2));}


int lineid=0;//0-index
vector<line> vline;
vector<tuple<db,db,db>> vabc;

int nodeid=0;//1-index
struct node{
	int tp;
	// 1 2 3 4 5
	// & | ^ ! L
	int lson;
	int rson;
	int line_num;
};
node vnode[200050];

int parse(const string &expr,int L,int R){
//	cerr << "----------------" << endl;
//	cerr << "expr : " << expr << endl;
//	cerr << "L R:" << L << " " << R << endl;
//	if (++__CNT==20) exit(0);
	if (expr[L]=='['){
		string tmp=expr.substr(L+1,R-L-1);
		stringstream ss(tmp);
		
		long long a,b,c;
		ss >> a >> b >> c;
		db D=-1.0*c/(a*a+b*b);
		point P={D*a,D*b};
		point dir={(db)b,(db)-a};
		point Q=P+dir.turn90();
		if (sign(a*Q.x+b*Q.y+c)<0) dir=dir*(-1.0);
		
		vline.emplace_back(P,P+dir);
		vabc.emplace_back(a,b,c);
		vnode[++nodeid]={5,-1,-1,lineid};
		lineid++;
		return nodeid;
	}
	if (expr[L+1]=='!'){
		int now_id=++nodeid;
		vnode[now_id]={4,parse(expr,L+2,R-1),-1,-1};
		return now_id;
	}
	int pos=-1;
	int sum=0;
	for (int i=L+1;i<=R-1;i++){
		if (expr[i]=='(') sum++;
		if (expr[i]=='[') sum++;
		if (expr[i]==')') sum--;
		if (expr[i]==']') sum--;
		if (sum==0){
			pos=i+1;
			break;	
		}
	}
//	cerr << "pos,sum: " << pos << " " << sum << endl; 
	int now_id=++nodeid;
	if (expr[pos]=='&') vnode[now_id].tp=1;
	if (expr[pos]=='|') vnode[now_id].tp=2;
	if (expr[pos]=='^') vnode[now_id].tp=3;
	vnode[now_id].lson=parse(expr,L+1,pos-1);
	vnode[now_id].rson=parse(expr,pos+1,R-1);
	vnode[now_id].line_num=-1;
	return now_id;
}

bool check(int x,point P){
	if (vnode[x].tp==1){
		return check(vnode[x].lson,P) && check(vnode[x].rson,P);
	}
	else if (vnode[x].tp==2){
		return check(vnode[x].lson,P) || check(vnode[x].rson,P);
	}
	else if (vnode[x].tp==3){
		return check(vnode[x].lson,P) ^ check(vnode[x].rson,P);
	}
	else if (vnode[x].tp==4){
		return !check(vnode[x].lson,P);
	}
	else if (vnode[x].tp==5){
		tuple<db,db,db> &abc = vabc[vnode[x].line_num];
		if (sign(get<0>(abc)*P.x+get<1>(abc)*P.y+get<2>(abc))>=0) return true;
		return false;
	}
	return false;
}

int main(){
	db xl,yl,xr,yr;
	cin >> xl >> xr >> yl >> yr;
	
	string expr;
	cin >> expr;
	int len=expr.length();
	for (auto &ch:expr) if (ch==',') ch=' ';
	int Root = parse(expr,0,len-1);
	
	point C1={(db)xl,(db)yl};
	point C2={(db)xr,(db)yl};
	point C3={(db)xr,(db)yr};
	point C4={(db)xl,(db)yr};
	vline.emplace_back(C1,C2);
	vline.emplace_back(C2,C3);
	vline.emplace_back(C3,C4);
	vline.emplace_back(C4,C1);
	lineid+=4;
	/*
	cerr << "stage 1" << endl;
	cerr << "---------------" << endl;
	cerr << "lineid : " << lineid << endl;
	for (auto L:vline) cerr << L << endl;
	cerr << "---------------" << endl;
	cerr << "nodeid : " << nodeid << endl;
	for (int i=1;i<=nodeid;i++)
		cerr << "tp,l,r,lid : "
			 << vnode[i].tp << " "
			 << vnode[i].lson << " "
			 << vnode[i].rson << " "
			 << vnode[i].line_num << endl;
	*/
	vector<point> vp;
	for (auto l1:vline){
		for (auto l2:vline){
			if (!checkLL(l1,l2)) continue;
			point tmp=getLL(l1,l2);
			if (!inmid(xl,xr,tmp.x)) continue;
			if (!inmid(yl,yr,tmp.y)) continue;
			vp.emplace_back(tmp);
		}
	}
	sort(vp.begin(),vp.end());
	vp.resize(
		unique(vp.begin(),vp.end())-vp.begin()
	);
	
	int pnum=vp.size();
	vector<vector<int>> G(pnum);
	/*
	cerr << "--------------" << endl;
	cerr << "stage 2" << endl;
	cerr << "point_num : " << pnum << endl;
	for (auto p:vp) cerr << p << endl;
	cerr << "--------------" << endl;
	*/
	for (auto l:vline){
		vector<int> ps;
		for (int i=0;i<pnum;i++)
			if (sign(cross(l[1]-l[0],vp[i]-l[0]))==0) ps.emplace_back(i);
		sort(ps.begin(),ps.end(),
			[&](int idx,int idy){
				return dot(l[1]-l[0],vp[idx]-l[0])<dot(l[1]-l[0],vp[idy]-l[0]);
			}
		);
		int sz=ps.size();
		for (int i=1;i<sz;i++){
			G[ps[i-1]].emplace_back(ps[i]);
			G[ps[i]].emplace_back(ps[i-1]);
		}
	}
	
	for (int i=0;i<pnum;i++){
		sort(
			G[i].begin(),G[i].end(),
			[&](int x,int y){
				return compareangle(vp[x]-vp[i],vp[y]-vp[i]);	
			}
		);
	}
	/*
	for (int i=0;i<pnum;i++){
		cerr << "G[" << i << "] : ";
		for (auto j:G[i]) cerr << j << " ";
		cerr << endl;	
	}
	*/
	db ans=0;
	set<pair<int,int>> vis;
	for (int i=0;i<pnum;i++){
		for (auto j:G[i]){
			if (vis.count(make_pair(i,j))) continue;
		//	cerr << "go : " << i << " " << j << endl;
			vector<point> area;
			
			int now=i;
			int nxt=j;
			do{
			//	cerr << "now,nxt : " << now << " " << nxt << endl;
				area.push_back(vp[now]);
				vis.emplace(make_pair(now,nxt));
				
				int nxt_nxt=-1;
				for (auto k:G[nxt]){
					if (sign(cross(vp[nxt]-vp[now],vp[k]-vp[nxt]))<=0) continue;
					if (vis.count(make_pair(nxt,k))) continue;
					
					if (nxt_nxt==-1) nxt_nxt=k;
					else if (sign(cross(vp[nxt_nxt]-vp[nxt],vp[k]-vp[nxt]))>0){
						nxt_nxt=k;
					}
				}
				
				now=nxt;
				nxt=nxt_nxt;
				
			}while (now!=i && nxt!=-1);
			
			int cnt=area.size();
			if (cnt<3) continue;
			
			point O={(db)0.0,(db)0.0};
			for (auto P:area) O=O+P;
			O=O/cnt;
			
			if (!check(Root,O)) continue; 
			
			db S=0;
			for (int k=2;k<cnt;k++) S=S+cross(area[k-1]-area[0],area[k]-area[0]);
			
			S=S/2;
			ans+=S;
			
		}
	}
	cout << fixed << setprecision(12) << ans << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3860kb

input:

0 1 0 1
([-1,1,0]^[-1,-1,1])

output:

0.500000000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #2:

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

input:

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

output:

70.451693404635

result:

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

Test #3:

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

input:

0 1 -1 1
([1,1,1]&[-1,-1,-1])

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

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

input:

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

output:

0.000500000000

result:

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

Test #5:

score: 0
Accepted
time: 1ms
memory: 3912kb

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.334852441477

result:

ok found '47063.3348524', expected '47063.3348524', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3936kb

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.058655663222

result:

ok found '36999.0586557', expected '36999.0586557', error '0.0000000'

Test #7:

score: -100
Wrong Answer
time: 233ms
memory: 17228kb

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:

294052.797674910655

result:

wrong answer 1st numbers differ - expected: '295728.6081036', found: '294052.7976749', error = '0.0056667'