QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293841 | #4005. Frog | rageOfThunder# | WA | 41ms | 3708kb | C++14 | 4.6kb | 2023-12-29 20:45:14 | 2023-12-29 20:45:15 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
const int mod=998244353;
int ksm(int x,int y,int p=mod){
int ans=1;
for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}
void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}
#define double long double
#define EPS 1e-9
int dcmp(double x){
if(fabs(x)<EPS)return 0;
if(x>0)return 1;
return -1;
}
struct P{
double x,y;
P(double X,double Y):x(X),y(Y){}
P(){}
};
#define pi acos(-1)
bool operator==(P A,P B){return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0;}
P rot(P A,int t){
// cout<<"rot "<<A.x<<" "<<A.y<<" "<<t<<endl;
if(t==0)return A;
if(t==90)return P(-A.y,A.x);
if(t==180)return P(-A.x,-A.y);
if(t==270)return P(A.y,-A.x);
if(t==360)return A;
double tt=t;double th=tt*pi/180.0;
// cout<<"th = "<<th<<endl;
return P(A.x*cos(th)-A.y*sin(th),A.x*sin(th)+A.y*cos(th));
}
bool inc(P A){return dcmp(A.x*A.x+A.y*A.y-1)==-1;}
double Cross(P A,P B){return A.x*B.y-A.y*B.x;}
double Dot(P A,P B){return A.x*B.x+A.y*B.y;}
P operator+(P A,P B){return P(A.x+B.x,A.y+B.y);}
P operator-(P A,P B){return P(A.x-B.x,A.y-B.y);}
P operator*(P A,double v){return P(A.x*v,A.y*v);}
P operator/(P A,double v){return P(A.x/v,A.y/v);}
bool Out(P A,P B,P C){
if(dcmp(Dot(C-B,A-B))<0||dcmp(Dot(B-C,A-C))<0)return true;
return false;
}
bool chk(P A,P B){
// cout<<"chk A = ("<<A.x<<","<<A.y<<") B = ("<<B.x<<","<<B.y<<")\n";
if(inc(A)||inc(B))return true;
// puts("ok1");
if(A==B)return dcmp(Dot(A,A)-1)<1;
if(Out(P(0,0),A,B))return false;
// puts("ok2");
double S=fabs(Cross(A,B));
double L=sqrt(Dot(A-B,A-B));
// cout<<"S = "<<S<<" L = "<<L<<endl;
return dcmp(S-L)<0;
}
P get(P A,P B,double t){
double s=sqrt(Dot(A-B,A-B));
return A+((B-A)*t/s);
}
P getP(P A,P B){
double L=sqrt(Dot(A-B,A-B));L/=2;
// cout<<"A = ("<<A.x<<","<<A.y<<") B = ("<<B.x<<","<<B.y<<")\n";
// cout<<"L = "<<L<<endl;
if(dcmp(L-1)>0)return P(114,514);
P C=P((A.x+B.x)/2.0,(A.y+B.y)/2.0);
L=sqrt(1-L*L);
// cout<<" -> L = "<<L<<endl;
P D=get(C,B,L);
// cout<<"D = ("<<D.x<<","<<D.y<<")"<<endl;
D=rot(D-C,90)+C;
return D;
}
int f;
void R(P &A){
if(fabs(A.x)<EPS)A.x=0;
if(fabs(A.y)<EPS)A.y=0;
// A.x=fabs(A.x),A.y=fabs(A.y);
}
void RR(P &A){
if(f==-1)A.y=-A.y;
}
signed main(void){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
#endif
cout.precision(8);
auto solve=[&](int st,int ed){
// cout<<"solve "<<st<<" "<<ed<<endl;
f=1;
ed-=st,ed=(ed+360)%360;
double tt=st;double th=tt*pi/180.0;
if(ed>180)ed=360-ed,f=-1;
// cout<<"now st,ed = "<<st<<" "<<ed<<endl;
double tted=ed;double eh=tted*pi/180.0;
if(ed==0){
puts("0");
P A=P(1,0);
RR(A);
A=rot(A,st);
R(A);
cout<<A.x<<" "<<A.y<<endl;
return ;
}
if(ed<=90){
P A=P(1,0);
P B=P(cos(eh),sin(eh));
if(ed==90)B=P(0,1);
P D=getP(B,A);
cout<<2<<endl;
// puts("========= cur =========");
// cout<<A.x<<" "<<A.y<<endl;
// cout<<D.x<<" "<<D.y<<endl;
// cout<<B.x<<" "<<B.y<<endl;
// cout<<"st = "<<st<<endl;
// puts("=======================");
RR(A),RR(B),RR(D);
A=rot(A,st),D=rot(D,st),B=rot(B,st);
R(A),R(D),R(B);
cout<<A.x<<" "<<A.y<<endl;
cout<<D.x<<" "<<D.y<<endl;
cout<<B.x<<" "<<B.y<<endl;
}
else{
P A=P(1,0);
P B=P(1,1);
P D=P(cos(eh),sin(eh));
if(ed==180)D=P(-1,0);
R(D);
P C=getP(D,B);
if(chk(C,D)||chk(B,C)){
C=P(0,1);
P E=getP(D,C);
RR(A),RR(B),RR(C),RR(D),RR(E);
A=rot(A,st),B=rot(B,st),C=rot(C,st),D=rot(D,st),E=rot(E,st);
puts("4");
R(A),R(B),R(C),R(D),R(E);
cout<<A.x<<" "<<A.y<<endl;
cout<<B.x<<" "<<B.y<<endl;
cout<<C.x<<" "<<C.y<<endl;
cout<<E.x<<" "<<E.y<<endl;
cout<<D.x<<" "<<D.y<<endl;
}
else{
RR(A),RR(B),RR(C),RR(D);
A=rot(A,st),B=rot(B,st),C=rot(C,st),D=rot(D,st);
R(A),R(B),R(C),R(D);
puts("3");
cout<<A.x<<" "<<A.y<<endl;
cout<<B.x<<" "<<B.y<<endl;
cout<<C.x<<" "<<C.y<<endl;
cout<<D.x<<" "<<D.y<<endl;
}
}
};
int tt=read();while(tt--){int st=read(),ed=read();solve(st,ed);}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
input:
3 0 0 0 90 180 0
output:
0 1 0 2 1 0 1 1 0 1 4 -1 0 -1 -1 0 -1 1 -1 1 0
result:
ok ok
Test #2:
score: -100
Wrong Answer
time: 41ms
memory: 3708kb
input:
10000 194 96 89 164 139 41 323 35 185 221 0 275 53 116 233 79 209 91 236 12 94 291 332 293 207 31 133 329 60 114 1 91 273 103 69 193 220 303 100 118 42 15 331 201 26 103 347 292 184 148 307 197 84 326 52 224 257 27 3 99 310 26 138 288 112 17 206 159 302 104 58 121 276 268 236 134 281 173 147 128 72 ...
output:
3 -0.97029573 -0.2419219 -1.2122176 0.72837383 -0.8503927 1.6606199 -0.10452846 0.9945219 2 0.017452406 0.9998477 -0.94380929 1.2754851 -0.9612617 0.27563736 3 -0.75470958 0.65605903 -0.098650551 1.4107686 0.87253497 1.6490934 0.75470958 0.65605903 2 0.79863551 -0.60181502 1.6177876 -0.028238587 0.8...
result:
wrong answer Jump #2 length too far from 1.000000 (Test case 11)