QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#354252#2885. 非欧几何CrysflyWA 63ms3848kbC++177.6kb2024-03-15 01:18:492024-03-15 01:18:49

Judging History

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

  • [2024-03-15 01:18:49]
  • 评测
  • 测评结果:WA
  • 用时:63ms
  • 内存:3848kb
  • [2024-03-15 01:18:49]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define double long double
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 400005
#define inf 0x3f3f3f3f

typedef double db;
const db eps=1e-10,pi=3.14159265358979323846;
int sgn(db x){return x<-eps?-1:x>eps;}
int cmp(db a,db b){return sgn(a-b);}

struct P{
	db x,y;
	P(db x=0,db y=0):x(x),y(y){}
	P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
	P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
	P&operator *=(db o){return x*=o,y*=o,*this;}
	P&operator /=(db o){return x/=o,y/=o,*this;}
	friend P operator +(P a,P b){return a+=b;}
	friend P operator -(P a,P b){return a-=b;}
	friend P operator *(P a,db b){return a*=b;}
	friend P operator /(P a,db b){return a/=b;}
	friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
	friend bool operator ==(P a,P b){return cmp(a.x,b.x)==0 && cmp(a.y,b.y)==0;}
	friend db operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
	friend db operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
	
	void rot(db o){
		db s=sin(o),c=cos(o),xx=x*c-y*s,yy=x*s+y*c;
		x=xx,y=yy;
	}
	void rot90(){swap(x,y),x=-x;}
	db ang(){return atan2(y,x);}
	db l(){return sqrt(x*x+y*y);}
	db l2(){return x*x+y*y;}
	
	int half(){return sgn(y)==1||(sgn(y)==0&&sgn(x)>=0);}
	P unit(){return ((*this))/l();}
	
	void read(){cin>>x>>y;}
	void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
bool cmp_dir(P a,P b){
	if(a.half()!=b.half())return a.half()<b.half();
	return sgn(a*b)>0;
}

db dis(P a,P b){return (a-b).l();}
db cross(P a,P b,P c){
	// (a->b)*(a->c)
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp3(P a,P b,P c){
	return sgn(cross(a,b,c));
}

bool chkl(P p1,P p2,P q1,P q2){
	// is parallel
	return sgn((p2-p1)*(q2-q1))==0;
}
P interl(P p1,P p2,P q1,P q2){
	// intersect point
	db s1=cross(q1,q2,p1),s2=-cross(q1,q2,p2);
	return (p1*s2+p2*s1)/(s1+s2);
}

bool inter(db l1,db r1,db l2,db r2){
	if(l1>r1)swap(l1,r1); if(l2>r2)swap(l2,r2);
	return !(cmp(r1,l2)==-1||cmp(r2,l1)==-1);
}
bool ismid(db a,db m,db b){
	return sgn(a-m)==0||sgn(b-m)==0||((a<m)!=(b<m));
}
bool ismid(P a,P m,P b){
	return ismid(a.x,m.x,b.x)&&ismid(a.y,m.y,b.y);
}

bool chkseg(P p1,P p2,P q1,P q2){
	return inter(p1.x,p2.x,q1.x,q2.x) && inter(p1.y,p2.y,q1.y,q2.y) &&
	cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<=0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<=0;
}
bool chkseg_strict(P p1,P p2,P q1,P q2){
	return cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<0;
}

struct L{
	P a,b;
	L(P aa,P bb){a=aa,b=bb;}
	bool isin(P p){return sgn((b-a)*(p-a))>0;}
	P dir(){return b-a;}
	bool onl(P p){
		return cmp3(a,b,p)==0;
	}
	bool onseg(P p){
		return onl(p)&&ismid(a,p,b);
	}
	bool onseg_strict(P p){
		return onl(p)&&sgn((p-a)%(a-b))*sgn((p-b)%(a-b))<0;
	}
	void out(){cout<<"("<<a.x<<","<<a.y<<")---("<<b.x<<","<<b.y<<")\n";}
};

bool chkl(L a,L b){
	// is parallel
	return chkl(a.a,a.b,b.a,b.b);
}
P operator &(L a,L b){
	return interl(a.a,a.b,b.a,b.b);
}
bool samedir(L a,L b){
	return chkl(a,b) && sgn(a.dir()%b.dir())==1;
}
bool operator <(L a,L b){
	if(samedir(a,b)) return b.isin(a.a);
	return cmp_dir(a.dir(),b.dir());
}

P proj(L a,P b){
	P d=a.dir();
	return a.a+d*((d%(b-a.a))/d.l2());
}
P reflect(L a,P b){
	return proj(a,b)*2-b;
}

db rad(P a,P b){
	return atan2l(a*b,a%b);
}

// polygon
db area(vector<P>a){
	db res=0;
	For(i,0,(int)a.size()-1)res+=a[i]*a[(i+1)%a.size()];
	return res/2;
}
int contain(vector<P>a,P p){
	int n=a.size(),res=0;
	For(i,0,n-1){
		P u=a[i],v=a[(i+1)%n];
		if(L(u,v).onseg(p))return 1;
		if(cmp(u.y,v.y)<=0)swap(u,v);
		if(cmp(p.y,u.y)>0 && cmp(p.y,v.y)<=0)continue;
		res^=cmp3(p,u,v)>0;
	}
	return res*2;
}
vector<P>cut(vector<P>a,P q1,P q2){
	vector<P>b; int n=a.size();
	For(i,0,n-1){
		P p1=a[i],p2=a[(i+1)%n];
		int d1=cmp3(q1,q2,p1),d2=cmp3(q1,q2,p2);
		if(d1>=0)b.pb(p1);
		if(d1*d2<0)b.pb(interl(p1,p2,q1,q2));
	}
	return b;
}

vector<P>convex(vector<P>a){
	int n=a.size(),m=0; if(n<=1)return a;
	sort(a.begin(),a.end());
	vector<P>st(n*2); int tp=0;
	For(i,0,n-1){
		while(tp>1 && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	int t=tp;
	Rep(i,n-2,0){
		while(tp>t && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	st.resize(tp-1);
	return st;
}
db diam(vector<P>a){
	int n=a.size();
	if(n<=1)return 0;
	int ii=0,jj=0;
	For(k,1,n-1){
		if(a[k]<a[ii])ii=k;
		if(a[jj]<a[k])jj=k;
	}
	int i=ii,j=jj;
	db res=dis(a[i],a[j]);
	do{
		if((a[(i+1)%n]-a[i])*(a[(j+1)%n]-a[j])>=0) (++j)%=n;
		else (++i)%=n;
		res=max(res,dis(a[i],a[j]));
	}while(i!=ii||j!=jj);
	return res;
}

bool check(L a,L b,L c){
	return c.isin(a&b);
}
deque<L>qtmp;
vector<P>hpis(vector<L>&l){
	sort(l.begin(),l.end());
	deque<L>q;
	For(i,0,(int)l.size()-1){
		if(i&&samedir(l[i],l[i-1]))continue;
		while(q.size()>1 && !check(q[q.size()-2],q[q.size()-1],l[i]))q.pop_back();
		while(q.size()>1 && !check(q[1],q[0],l[i]))q.pop_front();
		q.pb(l[i]);
	}
	while(q.size()>2 && !check(q[q.size()-2],q[q.size()-1],q[0]))q.pop_back();
	while(q.size()>2 && !check(q[1],q[0],q[q.size()-1]))q.pop_front();
	qtmp=q;
	vector<P>res;
	For(i,0,(int)q.size()-1) res.pb(q[i]&q[(i+1)%q.size()]);
	return res;
}

struct hull{
	vector<L>l1,l2;
	vector<P>p1,p2;
	deque<L>q1,q2;
	void ins(L t){
		P d=t.dir(); d.rot90();
		if(d.half()) l1.pb(t); // down hull
		else l2.pb(t); // up hull
	}
	void build(){
		if(l1.size()) p1=hpis(l1),q1=qtmp;
		if(l2.size()) p2=hpis(l2),q2=qtmp;
		reverse(p2.begin(),p2.end());
		For(i,1,SZ(p1)-1)assert(p1[i-1].x-eps<=p1[i].x);
		For(i,1,SZ(p2)-1)assert(p2[i-1].x-eps<=p2[i].x);
	}
	bool in(P x){
		if(l1.size()){
			if(!l1[0].isin(x))return 0;
			if(!l1.back().isin(x))return 0;
			auto it=lower_bound(ALL(p1),x);
			if(it!=p1.end()){
				P pl=*prev(it),pr=*it;
				if(!L(pl,pr).isin(x))return 0;
			}
		}
		if(l2.size()){
			if(!l2[0].isin(x))return 0;
			if(!l2.back().isin(x))return 0;
			auto it=lower_bound(ALL(p2),x);
			if(it!=p2.end()){
				P pl=*prev(it),pr=*it;
				if(!L(pr,pl).isin(x))return 0;
			}
		}
		For(i,1,SZ(p1)-1) if(!L(p1[i-1],p1[i]).isin(x)) return 0;
		For(i,1,SZ(p2)-1) if(!L(p2[i],p2[i-1]).isin(x)) return 0;
		for(auto l:q1) if(!l.isin(x)) return 0;
		for(auto l:q2) if(!l.isin(x)) return 0;
		return 1;
	}
}t1,t2;

int n,m,T;
db R;

P getp(){
	db x,y; cin>>x>>y;
	db z=sqrtl(R*R-x*x-y*y);
	char ch; cin>>ch;
	z=R*2/(R+(ch=='-'?z:-z));
	return P(x*z,y*z);
}
L getline(){
	P p1=getp(),p2=getp();
//	cout<<"p1: ";p1.out();
//	cout<<"p2: ";p2.out();
	L l=L(p1,p2);
	if(!l.isin(P(0,0))) l=L(p2,p1);
	assert(l.isin(P(0,0)));
	return l;
}

signed main()
{
	cin>>n>>m>>T>>R;
	while(n--) t1.ins(getline());
	while(m--) t2.ins(getline());
//	cout<<t1.in(P(0,0))<<" in1\n";
//	cout<<t2.in(P(0,0))<<" in2\n";
	while(T--) {
		P x=getp();
		if(!t1.in(x)) puts("Safe");
		else if(!t2.in(x)) puts("Goodbye");
		else puts("Passer");
	}
	return 0;
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 57ms
memory: 3848kb

input:

1 1 50000
999
-804.012 474.581 - -894.464 -375.820 +
752.540 412.051 - 495.305 819.650 -
-864.250 416.299 +
-996.067 72.641 -
-512.349 39.102 -
994.573 24.725 -
489.232 -507.604 -
260.906 872.539 -
78.106 972.376 +
-335.957 940.631 +
-881.629 469.742 -
-285.093 147.253 -
-461.010 883.355 -
-154.842 ...

output:

Safe
Safe
Passer
Goodbye
Passer
Passer
Passer
Safe
Safe
Passer
Safe
Passer
Goodbye
Passer
Goodbye
Passer
Goodbye
Passer
Passer
Goodbye
Passer
Passer
Passer
Goodbye
Passer
Passer
Passer
Passer
Safe
Passer
Goodbye
Goodbye
Passer
Passer
Safe
Passer
Goodbye
Passer
Goodbye
Passer
Goodbye
Passer
Passer
Go...

result:

ok 50000 lines

Test #2:

score: -100
Wrong Answer
time: 63ms
memory: 3784kb

input:

3 461 50000
974
784.457 476.700 + -960.282 70.145 +
-441.764 -849.753 - 619.289 642.106 +
-725.206 -535.036 + -945.974 -229.799 -
750.696 176.899 - -448.253 855.111 -
877.296 -422.525 + 973.309 -1.218 +
-319.904 914.620 + -944.529 -133.840 +
-591.199 747.520 + -390.694 -253.706 -
-604.604 693.495 + ...

output:

Passer
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Passer
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Passer
Safe
Goodbye
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Safe
Passer
Safe
Safe
Safe
Safe
Passer
Safe
Safe
Safe
Safe
Passer
Passer
Saf...

result:

wrong answer 1st lines differ - expected: 'Goodbye', found: 'Passer'