QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73310#4390. KeychainspoiAC ✓3ms3380kbC++113.8kb2023-01-23 17:49:572023-01-23 17:49:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-23 17:49:58]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3380kb
  • [2023-01-23 17:49:57]
  • 提交

answer

#include "iostream"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "queue"
#include "vector"
#include "queue"
#include "stack"
#include "ctime"
#include "set"
#include "map"
#include "cmath"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 2e5 + 10;
const double eps = 1e-7;
int n , m;

double hypot( double x , double y , double z ) {
	return sqrt( x * x + y * y + z * z );
}

struct poi {
	double x , y , z;
	void in( ) {
		int x1 , y1 , z1;
		scanf("%d%d%d",&x1,&y1,&z1);
		x = x1 , y = y1 , z = z1;
	}
	poi( ) {}
	poi( double x , double y , double z ) : x(x) , y(y) , z(z) {}
	poi operator + ( const poi& b ) {
		return poi( x + b.x , y + b.y , z + b.z );
	}
	poi operator - ( const poi& b ) {
		return poi( x - b.x , y - b.y , z - b.z );
	}
	poi operator * ( const double& b ) {
		return poi( b * x , b * y , b * z );
	}
	poi operator / ( const double& b ) {
		return poi( x / b , y / b , z / b );
	}
	poi ori( ) {
		return ( *this ) / hypot( x , y , z );
	}
	double dis( ) {
		return hypot( x , y , z );
	}
} O1 , O2 , V1 , V2 , C1 , C2;
double r1 , r2;

poi det( const poi& a , const poi& b ) {
	return poi( 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 poi& a , const poi& b ) {
	return a.x * b.x + a.y * b.y + a.z * b.z;
}

double det( double a , double b , double c , double d ) {
	return a * d - b * c;
}
pair<double,double> solve( double a1 , double b1 , double c1 , double a2 , double b2 , double c2 ) {
	return mp( det( c1 , b1 , c2 , b2 ) / det( a1 , b1 , a2 , b2 ) , det( a1 , c1 , a2 , c2 ) / det( a1 , b1 , a2 , b2 ) );
}


void solve() {
	int t;
	O1.in() , V1.in() , scanf("%d",&t);
	r1 = t;
	O2.in() , V2.in() , scanf("%d",&t);
	r2 = t;
	
	if( fabs( det( V1 , V2 ).dis() ) < eps ) {
		puts("No");
		return;
	}
	if( fabs( det( V1.x , V1.z , V2.x , V2.z ) ) > eps ) {
		C1.y = 0.5;
		auto re = solve( V1.x , V1.z , dot( V1 , O1 ) - V1.y * C1.y , V2.x , V2.z , dot( V2 , O2 ) - V2.y * C1.y );
		C1.x = re.fi , C1.z = re.se;
		
		
		C2.y = -0.5;
		re = solve( V1.x , V1.z , dot( V1 , O1 ) - V1.y * C2.y , V2.x , V2.z , dot( V2 , O2 ) - V2.y * C2.y );
		C2.x = re.fi , C2.z = re.se;
	} else if( fabs( det( V1.y , V1.z , V2.y , V2.z ) ) > eps ) {
		C1.x = 0.5;
		auto re = solve( V1.y , V1.z , dot( V1 , O1 ) - V1.x * C1.x , V2.y , V2.z , dot( V2 , O2 ) - V2.x * C1.x );
		C1.y = re.fi , C1.z = re.se;
		
		
		C2.x = -0.5;
		re = solve( V1.y , V1.z , dot( V1 , O1 ) - V1.x * C2.x , V2.y , V2.z , dot( V2 , O2 ) - V2.x * C2.x );
		C2.y = re.fi , C2.z = re.se;
	} else {
		C1.z = 0.5;
		auto re = solve( V1.x , V1.y , dot( V1 , O1 ) - V1.z * C1.z , V2.x , V2.y , dot( V2 , O2 ) - V2.z * C1.z );
		C1.x = re.fi , C1.y = re.se;
		
		
		C2.z = -0.5;
		re = solve( V1.x , V1.y , dot( V1 , O1 ) - V1.z * C2.z , V2.x , V2.y , dot( V2 , O2 ) - V2.z * C2.z );
		C2.x = re.fi , C2.y = re.se;
		
	}
	
	
	poi L = C2 - C1;
	poi F = det( L , V2 ) , tp = C2 - O2;
	poi S = F.ori() * ( dot( F , tp ) / hypot( F.x , F.y , F.z ) );
	double d = sqrt( r2 * r2 - S.dis( ) * S.dis() );
	
	poi P = O2 + S;
	poi P1 = P + L.ori() * d , P2 = P - L.ori() * d;
	
	if( ( ( P1 - O1 ).dis() < r1 ) ^ ( ( P2 - O1 ).dis() < r1 ) ) puts("Yes");
	else puts("No");
}

signed main() {
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3380kb

input:

1000
30 -39 -96 941 -777 -411 410
618 -648 -252 -360 -408 -154 259
106 -454 754 -435 446 -146 53
856 -987 -123 -164 367 -117 384
-41 -366 -776 -658 473 93 81
-615 -987 107 616 999 762 512
-865 -570 737 245 -313 -916 323
-307 -496 -348 31 332 803 610
-475 907 181 763 979 -919 77
858 119 420 -884 -369...

output:

No
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
...

result:

ok 1000 lines