• <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>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594

            POJ 1410 Intersection---計算幾何

            Posted on 2009-10-02 03:13 Uriel 閱讀(398) 評論(0)  編輯 收藏 引用 所屬分類: POJ 、計算幾何
            判斷矩形與一線段是否相交,注意線段在矩形內部的情況
            其他都是模板。。沒什么了。。
            /*Problem: 1410  User: Uriel 
               Memory: 172K  Time: 0MS 
               Language: C++  Result: Accepted
            */
             

            #include
            <stdio.h>
            #include
            <stdlib.h>
            #include 
            <math.h>
            #define eps 1e-8
            #define zero(x) (((x)>0?(x):-(x))<eps)

            struct point
            {
                
            double x,y;
            }
            ;

            struct line
            {
                point a,b;
            }
            ;

            double xmult(point p1,point p2,point p0)
            {
                
            return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
            }


            int dot_online_in(point p,point l1,point l2)
            {
                
            return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
            }


            int dots_inline(point p1,point p2,point p3)
            {
                
            return zero(xmult(p1,p2,p3));
            }


            int same_side(point p1,point p2,point l1,point l2)
            {
                
            return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
            }


            int intersect_in(point u1,point u2,point v1,point v2)
            {
                
            if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
                
            {
                    
            return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
                }

                
            return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);
            }


            point P1,P2,S1,S2,S3,S4;

            int main()
            {
                
            int t,flag;
                
            double temp;
                scanf(
            "%d",&t);
                
            while(t--)
                
            {
                    scanf(
            "%lf %lf %lf %lf %lf %lf %lf %lf",&P1.x,&P1.y,&P2.x,&P2.y,&S1.x,&S1.y,&S2.x,&S2.y);
                    
            if(S1.x>S2.x)
                    
            {
                        temp
            =S1.x;
                        S1.x
            =S2.x;
                        S2.x
            =temp;
                    }

                    
            if(S1.y<S2.y)
                    
            {
                        temp
            =S1.y;
                        S1.y
            =S2.y;
                        S2.y
            =temp;    
                    }

                    S3.x
            =S1.x;
                    S3.y
            =S2.y;  
                    S4.x
            =S2.x;
                    S4.y
            =S1.y;
                    flag
            =0;
                    
            if(intersect_in(P1,P2,S1,S3) || intersect_in(P1,P2,S1,S4) || intersect_in(P1,P2,S2,S3) || intersect_in(P1,P2,S2,S4))
                    
            {
                        flag
            =1;
                    }

                    
            if(P1.x>=S1.x && P1.x<=S2.x && P2.x>=S1.x && P2.x<=S2.x && P1.y<=S1.y && P1.y>=S2.y && P2.y<=S1.y && P2.y>=S2.y)
                    
            {
                        flag
            =1;
                    }

                    
            if(!flag)
                    
            {
                        printf(
            "F\n");
                    }

                    
            else
                    
            {
                        printf(
            "T\n");
                    }

                }

            //    system("PAUSE");
                return 0;
            }

            久久影院久久香蕉国产线看观看| 精品久久久久久无码专区不卡| 国产精品内射久久久久欢欢| 亚洲国产精品婷婷久久| 久久国产精品免费一区二区三区 | 久久香蕉综合色一综合色88| 久久艹国产| 久久久久99精品成人片试看| 伊人久久大香线焦综合四虎| 最新久久免费视频| 久久国产成人精品麻豆| 人人狠狠综合久久亚洲| 久久精品无码一区二区无码| 久久人妻少妇嫩草AV蜜桃| 国产成人久久精品一区二区三区| 理论片午午伦夜理片久久| 久久不见久久见免费视频7| 久久久久亚洲AV无码专区桃色| 久久丫精品国产亚洲av| 狠狠色丁香久久婷婷综合_中 | 久久久久久综合一区中文字幕| 久久精品综合网| 亚洲а∨天堂久久精品| 久久精品国产精品青草| 日韩人妻无码精品久久久不卡 | 亚洲午夜福利精品久久| 青青青青久久精品国产| 国产成人精品久久免费动漫| 性欧美大战久久久久久久久| 日韩欧美亚洲综合久久影院Ds| 国产成人精品久久一区二区三区av| 亚洲AV日韩精品久久久久| 97精品国产97久久久久久免费| 亚洲精品无码久久毛片| 欧美日韩精品久久免费| 久久伊人五月丁香狠狠色| 日本亚洲色大成网站WWW久久 | 精品熟女少妇av免费久久| 久久人人爽人人爽人人片AV不 | 久久久久久久久66精品片| 色综合久久88色综合天天 |