• <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算法程序設(shè)計(jì)空間

            // 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 閱讀(2221) 評(píng)論(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.解一元二次方程要會(huì)吧!系數(shù)A,B,C的判定不要漏掉
            3.特殊情況下A=B=C什么時(shí)候有解考慮清楚

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

            #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无码| 无码任你躁久久久久久老妇| 波多野结衣久久一区二区| 国产精品成人久久久久三级午夜电影 | 亚洲国产天堂久久综合网站 | 久久精品国产亚洲AV无码偷窥| 久久精品成人欧美大片| 亚洲乱码精品久久久久.. | 国产免费久久精品99久久| 久久精品成人免费观看97| 久久无码精品一区二区三区| 色综合久久综合网观看| 久久高清一级毛片| 欧美精品乱码99久久蜜桃| 国产午夜福利精品久久2021| 久久这里只有精品首页| 欧美性猛交xxxx免费看久久久| 欧美精品国产综合久久| 精品久久一区二区| 中文字幕久久精品| 人妻无码精品久久亚瑟影视| 久久久国产精华液| 亚洲午夜精品久久久久久人妖| 99久久国产亚洲综合精品| 成人午夜精品久久久久久久小说| 久久久久AV综合网成人| 久久人人爽人人爽人人爽| 亚洲日本va午夜中文字幕久久| 国产高潮国产高潮久久久91 | 亚洲日韩中文无码久久| 久久久久久久亚洲精品| 丁香五月综合久久激情| AAA级久久久精品无码区| 日韩亚洲欧美久久久www综合网 | 国产精品成人99久久久久| 久久综合综合久久狠狠狠97色88| 国产精品一区二区久久国产| 久久精品国产69国产精品亚洲| 国产精品视频久久久| 99久久国语露脸精品国产| 99久久免费国产精精品|