QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209076#6763. Triangle Pendantucup-team1004WA 2ms3932kbC++143.3kb2023-10-10 09:15:262023-10-10 09:15:28

Judging History

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

  • [2023-10-10 09:15:28]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3932kb
  • [2023-10-10 09:15:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
int T,x[3],a,b,c;
struct vec{
	double x,y,z;
	vec(double a=0,double b=0,double c=0):x(a),y(b),z(c){}
};
ostream& operator << (ostream &out,const vec &x){
	return out<<'('<<x.x<<','<<x.y<<','<<x.z<<')';
}
vec operator + (const vec &a,const vec &b){
	return vec(a.x+b.x,a.y+b.y,a.z+b.z);
}
vec operator - (const vec &a,const vec &b){
	return vec(a.x-b.x,a.y-b.y,a.z-b.z);
}
vec operator / (const vec &a,const double &k){
	return vec(a.x/k,a.y/k,a.z/k);
}
vec operator * (const vec &a,const double &k){
	return vec(a.x*k,a.y*k,a.z*k);
}
vec cross(const vec &a,const vec &b){
	return vec(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);
}
double dot(const vec &a,const vec &b){
	return a.x*b.x+a.y*b.y+a.z*b.z;
}
double dis(const vec &a){
	return sqrt(dot(a,a));
}
int cur[3];
double d,ans[3];
void solve1(int x,int y,int z,int a,int b,int c,vector<int>cur){
	if(abs(x-y)>=c||abs(x-z)>=b||abs(y-z)>=a)return;
	vec A(0,0,0),B(c,0,0),C,D;
	C.z=0,C.x=1.0*(b*b-a*a+c*c)/(c*2),C.y=sqrt(b*b-C.x*C.x);
	D.x=1.0*(x*x+c*c-y*y)/(c*2);
	D.y=(y*y-z*z+pow(D.x-C.x,2)-pow(D.x-c,2)+C.y*C.y)/(2*C.y);
	D.z=sqrt(x*x-D.x*D.x-D.y*D.y);
	vec O=(A+B+C)/3,n1=cross(O-D,A-O)/dis(O-D),n2=cross(O-D,B-O)/dis(O-D);
	vec n=cross(n1,n2)/dis(n1);
	auto calc=[&](vec P){
		return dot(P-D,n)/dis(n);
	};
	if(calc(O)>0)n=n*(-1);
	if(calc(O)<d){
		d=calc(O);
		ans[cur[0]]=calc(A),ans[cur[1]]=calc(B),ans[cur[2]]=calc(C);
	}
}
void solve2(int c,int a,int b,int x,int y,vector<int>cur){
	if(abs(x-y)>=c)return;
	// debug("ok");
	vec A(0,0,0),B(c,0,0),C,D;
	C.z=0,C.x=1.0*(b*b-a*a+c*c)/(c*2),C.y=sqrt(b*b-C.x*C.x);
	D.z=0,D.x=1.0*(x*x-y*y+c*c)/(c*2),D.y=-sqrt(x*x-D.x*D.x);
	if(dis(A-D)>::x[cur[0]]||dis(B-D)>::x[cur[1]]||dis(C-D)>::x[cur[2]])return;
	vec O=(A+B+C)/3,n=O-D;
	auto calc=[&](vec P){
		return dot(P-D,n)/dis(n);
	};
	if(calc(O)>0)n=n*(-1);
	if(calc(O)<d){
		d=calc(O);
		ans[cur[0]]=calc(A),ans[cur[1]]=calc(B),ans[cur[2]]=calc(C);
	}
}
void solve3(int a,int b,int c,int x,vector<int>cur){
	vec A(0,0,0),B(c,0,0),C,D;
	C.z=0,C.x=1.0*(b*b-a*a+c*c)/(c*2),C.y=sqrt(b*b-C.x*C.x);
	vec O=(A+B+C)/3,m=A-O;
	D=A+m/dis(m)*x;
	if(dis(A-D)>::x[cur[0]]||dis(B-D)>::x[cur[1]]||dis(C-D)>::x[cur[2]])return;
	// debug(A,B,C,D);
	vec n=O-D;
	auto calc=[&](vec P){
		return dot(P-D,n)/dis(n);
	};
	if(calc(O)>0)n=n*(-1);
	if(calc(O)<d){
		d=calc(O);
		ans[cur[0]]=calc(A),ans[cur[1]]=calc(B),ans[cur[2]]=calc(C);
	}
}
void get(){
	scanf("%d%d%d%d%d%d",&x[0],&x[1],&x[2],&a,&b,&c);
	d=0;
	solve1(x[0],x[1],x[2],a,b,c,{0,1,2});
	solve2(a,b,c,x[1],x[2],{1,2,0});
	solve2(b,c,a,x[2],x[0],{2,0,1});
	solve2(c,a,b,x[0],x[1],{0,1,2});
	solve3(a,b,c,x[0],{0,1,2});
	solve3(b,c,a,x[1],{1,2,0});
	solve3(c,a,b,x[2],{2,0,1});
	// debug(d);
	for(int i=0;i<3;i++)printf("%.15lf%c",ans[i],"\n "[i<2]);
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
1 1 1 1 1 1
2 3 3 1 1 1

output:

-0.816496580927726 -0.816496580927726 -0.816496580927726
-2.000000000000000 -2.866025403784439 -2.866025403784439

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3932kb

input:

1000
21 2 14 12 13 4
29 19 13 15 10 17
29 24 15 29 24 23
29 17 30 18 9 25
27 24 30 16 4 15
28 13 17 12 21 16
16 22 10 22 15 8
15 23 24 23 27 13
26 3 27 15 16 17
5 8 20 17 6 12
24 14 13 15 19 13
27 22 18 18 23 30
22 18 14 11 29 28
7 13 22 22 17 11
19 9 16 22 20 17
21 14 20 6 29 25
20 10 19 9 27 27
17...

output:

-2.935856727586833 -2.000000000000000 -13.352348999857673
-22.146476218003023 -16.076204705476879 -12.241826659011300
-28.027431433359666 -18.318582636182793 -8.243362186282258
-27.266119651334364 -13.159319584325656 -26.882525397692710
-26.534933366925667 -22.066632132649342 -29.616079568529663
-26...

result:

wrong answer 25th numbers differ - expected: '-18.04415', found: '-10.93310', error = '0.39409'