SRM401 Medium: ParticleCollision
(問題概要)
省略(直線or点と螺旋の交点)
(解法)
直線によって超場合分け。
基本的には円と直線の交点だして、螺旋に乗ってるか判定。
こういう問題苦手。何度も再提出。
#include <cstdio> #include <complex> #include <cstdlib> #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std; class ParticleCollision { public: vector <double> collision(int vx, int vy, int vz, int x0, int y0, int z0); }; using std::complex; typedef complex<double> P; static inline double outp(const P &a, const P &b){ return (conj(a)*b).imag(); } class Line{ public: P p; /* position */ P d; /* direction */ Line(){} Line(P pos, P dir){p=pos; d=dir/abs(dir);} }; Line LineDirect(P pos, P dir){ return Line(pos, dir); } double dist(const Line &l, const P &p){ return std::abs(outp(l.d, p-l.p) / abs(l.d)); } const double EPS = 1e-9; const double PI = 3.14159265358979323846; vector <double> ParticleCollision::collision(int vx, int vy, int vz, int x0, int y0, int z0){ vector<double> ret; if(vx == 0 && vy == 0){ if((std::abs(x0) == 1 && y0 == 0) || (std::abs(y0) == 1 && x0 == 0) ){ if(vz == 0){ if(std::abs(P(x0, y0) - P(cos(PI * z0), sin(PI * z0))) < EPS){ ret.push_back(x0); ret.push_back(y0); ret.push_back(z0); } }else{ ret.push_back(0); ret.push_back(0); ret.push_back(0); } } }else{ const P o(0.0, 0.0); const Line l = LineDirect(P(x0, y0), P(vx, vy)); const double d = dist(l, o); if(d < 1.0 + EPS){ P dir = l.d * P(0, 1); P p1 = dir * d + l.d / std::abs(l.d) * sqrt(1 - d * d); P p2 = dir * d - l.d / std::abs(l.d) * sqrt(1 - d * d); if(dist(l, p1) > EPS || dist(l, p2) > EPS){ dir *= -1; p1 = dir * d + l.d / std::abs(l.d) * sqrt(1 - d * d); p2 = dir * d - l.d / std::abs(l.d) * sqrt(1 - d * d); } if(dist(l, p1) > EPS || dist(l, p2) > EPS) throw 0; const double t1 = ((p1 - P(x0, y0)) / P(vx, vy)).real(); const double t2 = ((p2 - P(x0, y0)) / P(vx, vy)).real(); const double z1 = z0 + vz * t1; const double z2 = z0 + vz * t2; if(std::abs(p1 - P(cos(PI * z1), sin(PI * z1))) < EPS){ ret.push_back(p1.real()); ret.push_back(p1.imag()); ret.push_back(z1); } if(std::abs(p1 - p2) > EPS){ if(std::abs(p2 - P(cos(PI * z2), sin(PI * z2))) < EPS){ ret.push_back(p2.real()); ret.push_back(p2.imag()); ret.push_back(z2); } } if(ret.size() > 3){ ret.resize(0); ret.push_back(0); ret.push_back(0); ret.push_back(0); } } } return ret; }