Problem Statement
|
| |
Particles
(which can be considered points in 3D-space for the purposes of the
problem) can move in an electro-magnetic field. If a particle is
charged, its trajectory can be described as spiral, and if it is
uncharged, it is just a straight line. Given two particles (one charged
and one uncharged) it should be determined whether they can possibly
collide or not. Two particles can possibly collide if and only if their
trajectories intersect.
Some steps have already been made by the physicist to simplify the
problem, so the coordinates of the charged particle are represented as
follows:
x1 = cos(PI * t)
y1 = sin(PI * t)
z1 = t
and for the uncharged particle:
x2 = vx * t + x0
y2 = vy * t + y0
z2 = vz * t + z0
Here t is a parameter which can be chosen arbitrarily and independently for both trajectories.
Your method will be given 6 integers - vx, vy, vz, x0, y0 and z0,
describing the trajectory of the uncharged particle. It should
determine whether the two given trajectories intersect or not. If they
do, it should return a vector <double> containing exactly 3
elements x, y and z - the coordinates of the point where a collision
can happen. If there is more than one such point, it should return a
vector <double> containing exactly three zeroes. If collision of
the two particles is impossible it should return an empty vector
<double>.
|
Definition
|
| |
| Class: |
ParticleCollision |
| Method: |
collision |
| Parameters: |
int, int, int, int, int, int |
| Returns: |
vector <double> |
| Method signature: |
vector <double> collision(int vx, int vy, int vz, int x0, int y0, int z0) |
| (be sure your method is public) |
|
| |
|
Notes
|
| - |
PI can be considered equal to 3.14159265358979323846. |
| - |
All return values with either an absolute or relative error of less than 1.0E-9 are considered correct. |
Constraints
|
| - |
vx, vy and vz will each be between -10 and 10, inclusive. |
| - |
x0, y0 and z0 will each be between -10 and 10, inclusive. |
Examples
|
| 0) |
|
| |
|
|
Returns: { }
|
| The second trajectory is a single point (0, 0, 0), which doesn't lie on the first trajectory. |
|
|
| 1) |
|
| |
|
|
Returns: {0.0, 1.0, 0.5 }
|
| There is a single intersection point with coordinates (0, 1, 0.5). |
|
|
| 2) |
|
| |
|
|
Returns: {0.0, 0.0, 0.0 }
|
| There are two intersection points. |
|
|
| 3) |
|
| |
|
|
Returns: {0.0, 0.0, 0.0 }
|
| There are infinitely many intersection points. |
|
|
This
problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this information
without the prior written consent of TopCoder, Inc. is strictly
prohibited. (c)2003, TopCoder, Inc. All rights reserved.
要做這道題，要注意很多問題：
1.看清題，題目中說了t是independent
2.解一元二次方程要會吧！系數A,B,C的判定不要漏掉
3.特殊情況下A=B=C什么時候有解考慮清楚
這樣你就可以過題了?。。?br>
#pragma warning ( disable : 4786 )
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <queue>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
const double PI = acos(-1.0);
#define sz(x) ((int)(x).size())
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define MAXINT 1000000000
#define EPS 1e-8
#define FOR(a,b,c) for(a=(b);(a)<(c);++(a))
#define REP(a,b) FOR(a,0,b)
typedef vector<int> VI;
inline int dblcmp(double a, double b) {
if(fabs(a-b) < EPS) return 0;
return a < b ? -1 : 1;
}
//typedef long long LL;
/*
cos(PI * t1)=vx * t2 + x0
sin(PI * t1)=vy * t2 + y0
t1=vz*t2+z0
*/
class ParticleCollision
{
public:
int vx, vy, vz, x0, y0, z0;
bool check(double t2) {
double x2 = vx * t2 + x0;
double y2 = vy * t2 + y0;
double t1 = vz * t2 + z0;
if(dblcmp(cos(PI * t1), vx * t2 + x0)==0
&& dblcmp(sin(PI * t1),vy * t2 + y0)==0
&& dblcmp(t1,vz*t2+z0)==0)
return true;
return false;
}
vector <double> collision(int _vx, int _vy, int _vz, int _x0, int _y0, int _z0)
{
vz=1;
vx = _vx;
vy = _vy;
vz = _vz;
x0 = _x0;
y0 = _y0;
z0 = _z0;
vector<double> mul(3, 0.0);
vector<double> empty;
int i, j;
double a = vx*vx + vy*vy;
double b = 2 * vx * x0 + 2 * vy * y0;
double c = x0 * x0 + y0 * y0 - 1;
// printf("a = %lf b = %lf c = %lf\n", a, b, c);
double det = b*b-4 * a * c;
if(dblcmp(a, 0.0) == 0) {
if(dblcmp(b, 0.0) == 0) {
if(dblcmp(c, 0.0) == 0) {
if(dblcmp(vz, 0.0) == 0) {
if(dblcmp(x0, cos(PI * z0)) == 0
&& dblcmp(y0, sin(PI * z0)) == 0) {
vector<double> ret;
ret.push_back(x0);
ret.push_back(y0);
ret.push_back(z0);
return ret;
}
}
else return mul;
}
return empty;
}
double t = -c / b;
if(check(t)) {
vector<double> ret;
ret.push_back(vx * t + x0);
ret.push_back(vy * t + y0);
ret.push_back(vz * t + z0);
return ret;
}
return empty;
}
// printf("det = %lf\n", det);
int x = dblcmp(det, 0);
if(x == 1) {
int cnt = 0;
vector<double> ret;
for(i = 0; i < 2; ++i) {
double t;
if(i == 0) t = (-b - sqrt(det)) / 2 / a;
if(i == 1) t = (-b + sqrt(det)) / 2 / a;
if(check(t)) {
ret.push_back(vx * t + x0);
ret.push_back(vy * t + y0);
ret.push_back(vz * t + z0);
cnt++;
}
}
if(cnt == 0) return empty;
else if(cnt == 1) return ret;
else return mul;
}
else if( x== -1) return empty;
else {
double t = (-b + sqrt(det)) / 2 / a;
if(check(t)) {
vector<double> ret;
ret.push_back(vx * t + x0);
ret.push_back(vy * t + y0);
ret.push_back(vz * t + z0);
return ret;
}
return empty;
}
}
};
// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor