QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293841#4005. FrogrageOfThunder#WA 41ms3708kbC++144.6kb2023-12-29 20:45:142023-12-29 20:45:15

Judging History

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

  • [2023-12-29 20:45:15]
  • 评测
  • 测评结果:WA
  • 用时:41ms
  • 内存:3708kb
  • [2023-12-29 20:45:14]
  • 提交

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)