• <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
             
            国产成人久久精品区一区二区| 亚洲国产日韩欧美久久| 91麻豆国产精品91久久久| 超级碰碰碰碰97久久久久| 国产精品99久久久精品无码| A级毛片无码久久精品免费| 99久久99久久| 美女久久久久久| 久久91精品国产91久久户| 亚洲国产精品综合久久一线| 色婷婷久久综合中文久久蜜桃av| 国产精品成人无码久久久久久| 久久天天躁狠狠躁夜夜avapp| 品成人欧美大片久久国产欧美...| 欧美与黑人午夜性猛交久久久| 久久精品视频网| 亚洲精品蜜桃久久久久久| 久久国产免费直播| AV无码久久久久不卡网站下载 | 一本久久a久久精品综合香蕉| 久久精品成人欧美大片| 久久久久久噜噜精品免费直播 | 中文字幕久久欲求不满| 欧美黑人激情性久久| 日韩十八禁一区二区久久| 色综合久久精品中文字幕首页| 国产精品久久久久无码av| 久久99久国产麻精品66| 日本加勒比久久精品| 国产精品九九久久免费视频 | 亚洲国产另类久久久精品| 久久国产成人午夜aⅴ影院| 99久久精品免费看国产一区二区三区 | 久久99精品国产| 99久久成人国产精品免费| 久久99亚洲网美利坚合众国| 狠狠色婷婷久久一区二区| 久久夜色精品国产网站| 国内精品久久久人妻中文字幕| 99久久人妻无码精品系列蜜桃 | 国产三级观看久久|