QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#354251 | #2885. 非欧几何 | Crysfly | TL | 74ms | 4036kb | C++17 | 7.5kb | 2024-03-15 01:16:40 | 2024-03-15 01:16:41 |
Judging History
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);
}
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();
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;
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);
if(l2.size()) p2=hpis(l2);
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:l1) if(!l.isin(x)) return 0;
for(auto l:l2) 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: 44ms
memory: 3960kb
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: 0
Accepted
time: 74ms
memory: 3840kb
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:
Goodbye 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 Goodbye Safe Goodbye Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Goodbye Safe Safe Safe Safe Goodbye Safe Safe Safe Safe Goodbye Passe...
result:
ok 50000 lines
Test #3:
score: 0
Accepted
time: 48ms
memory: 4036kb
input:
9 463 50000 973 597.967 -639.060 - 874.803 401.447 - -934.763 -262.127 + -912.888 -296.158 - 142.010 292.850 - -311.595 -871.137 - -912.339 -94.077 - -604.834 -672.595 - -189.196 759.979 - -705.801 666.122 + -381.831 -842.537 - 872.112 -351.678 + -243.291 -645.668 - -511.155 -733.734 + -712.134 646....
output:
Safe Goodbye Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Goodbye Safe Safe Safe Safe Safe Safe Safe Safe Safe Goodbye Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Goodbye Safe Safe Goodbye Safe Safe ...
result:
ok 50000 lines
Test #4:
score: 0
Accepted
time: 52ms
memory: 3836kb
input:
39 486 50000 956 -631.839 -689.747 - -600.713 -33.146 - -952.704 6.635 - -194.908 -726.891 - 521.450 -557.051 - 592.847 650.787 + -240.757 -380.448 - 526.354 -792.424 + -806.020 -282.992 - 398.047 820.829 - 384.098 833.019 + 14.147 -709.910 - -619.025 -567.568 - -954.972 -29.010 + 869.213 -359.593 +...
output:
Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe ...
result:
ok 50000 lines
Test #5:
score: 0
Accepted
time: 48ms
memory: 3844kb
input:
456 481 50000 990 805.321 206.787 - -19.086 868.502 - 594.224 -789.196 + -682.976 -705.637 - 957.919 217.646 + -372.489 859.053 - -32.358 646.155 - -783.001 -506.924 + -749.149 -620.973 + 910.744 380.617 - -111.543 -810.268 - 316.279 -937.961 - -356.665 -913.256 - 743.354 641.227 + -325.560 -922.361...
output:
Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe 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 Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Saf...
result:
ok 50000 lines
Test #6:
score: 0
Accepted
time: 55ms
memory: 3840kb
input:
471 486 50000 967 -219.415 -928.067 - -816.892 482.148 - 347.635 204.173 - 610.572 -611.533 + 863.572 399.514 - -36.683 -961.468 + -603.797 -674.752 + 21.298 773.196 - 815.770 58.560 - 692.242 611.125 + -570.167 -779.921 + 599.130 -512.308 - 341.883 -897.692 + 463.720 -822.205 - 965.987 -35.287 - -1...
output:
Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe Safe ...
result:
ok 50000 lines
Test #7:
score: -100
Time Limit Exceeded
input:
5000 5000 131203 959 935.958 167.112 - 166.090 -280.895 - 912.979 292.183 - 470.358 -652.661 - 239.573 -908.710 + -192.308 -932.148 + -893.651 -347.780 - -685.065 -648.438 + 116.122 907.590 - 728.164 444.732 - -520.051 739.395 + -772.285 567.793 - -836.485 466.444 - -706.621 628.223 - 886.392 364.29...
output:
Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer Passer...