• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            SRM401 550 PTS ParticleCollision

            Posted on 2008-05-07 02:32 oyjpart 閱讀(2219) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            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)
                
            0
            0
            0
            0
            0
            0
            Returns: { }
            The second trajectory is a single point (0, 0, 0), which doesn't lie on the first trajectory.
            1)
                
            2
            4
            1
            -1
            -1
            0
            Returns: {0.0, 1.0, 0.5 }
            There is a single intersection point with coordinates (0, 1, 0.5).
            2)
                
            4
            4
            2
            5
            4
            0
            Returns: {0.0, 0.0, 0.0 }
            There are two intersection points.
            3)
                
            0
            0
            1
            1
            0
            0
            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什么時候有解考慮清楚

            這樣你就可以過題了!!!

            #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
             
            久久大香香蕉国产| 无码乱码观看精品久久| 久久成人小视频| 久久人人爽人人爽人人片AV东京热 | 成人久久免费网站| 国产成人精品久久综合| 久久久久久极精品久久久| 中文字幕日本人妻久久久免费 | 99久久综合国产精品免费| 伊人久久大香线蕉精品不卡| 久久精品人人做人人爽97| 欧美伊香蕉久久综合类网站| 亚洲国产精品无码久久一区二区 | 亚洲精品国产自在久久| 无码伊人66久久大杳蕉网站谷歌| 成人a毛片久久免费播放| 99久久精品国产一区二区| 国内精品久久久久国产盗摄| 国产成人精品久久二区二区| 人妻无码精品久久亚瑟影视| 色成年激情久久综合| 一本一本久久aa综合精品 | 国产精品久久亚洲不卡动漫| 久久久久国产一级毛片高清板| a高清免费毛片久久| 久久久无码精品亚洲日韩按摩| 日韩中文久久| 久久国产高清一区二区三区| 亚洲天堂久久精品| 久久久久亚洲AV成人网人人网站 | 久久精品成人| 99久久精品国产免看国产一区| 一本大道久久香蕉成人网| 久久久噜噜噜久久| 久久一区二区三区99| 久久久久九九精品影院| 久久综合五月丁香久久激情| 久久国产V一级毛多内射| 久久久久国产一区二区| 少妇被又大又粗又爽毛片久久黑人 | 久久久久四虎国产精品|