• <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
             
            国产成人久久精品激情| 精品免费久久久久国产一区| 综合久久国产九一剧情麻豆| 久久久久久久人妻无码中文字幕爆 | 国内精品久久久久| 亚洲欧洲精品成人久久曰影片| 精品综合久久久久久97| 久久综合九色综合久99| 精品久久久久久久久免费影院| 久久无码人妻一区二区三区 | 久久久精品国产sm调教网站 | 亚洲美日韩Av中文字幕无码久久久妻妇| 精品综合久久久久久97| 国内精品久久久久久久涩爱| 久久水蜜桃亚洲av无码精品麻豆| 久久精品国产精品亚洲下载| 久久AV高清无码| 99久久夜色精品国产网站| 久久精品中文字幕一区| 精品久久久久久久久中文字幕| 国内高清久久久久久| 中文字幕久久精品| 久久精品国产99久久香蕉| 久久国产精品一区二区| 99999久久久久久亚洲| 一本色道久久综合亚洲精品| 亚洲国产成人精品女人久久久| 国产亚洲成人久久| 成人精品一区二区久久| 久久国产精品成人免费| 99久久综合狠狠综合久久止| 久久99亚洲网美利坚合众国| 久久九九精品99国产精品| 无码人妻久久一区二区三区免费| 久久久久久久久久久久久久| 伊人久久大香线蕉精品不卡| 日产精品久久久久久久| 少妇高潮惨叫久久久久久| 久久精品国产99久久无毒不卡| 精品国产乱码久久久久久郑州公司| 亚洲AV成人无码久久精品老人|