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

            求多邊形的核

             

            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-8-10 11:46:29
            File Name: pku3335.cpp
            Description: 
            ***********************************************************************
            */

            #include 
            <algorithm>
            #include 
            <iostream>
            #include 
            <sstream>
            #include 
            <string>
            #include 
            <queue>
            #include 
            <list>
            #include 
            <set>
            #include 
            <map>
            #include 
            <cmath>
            #include 
            <vector>
            #include 
            <cctype>
            #include 
            <cstring>
            using namespace std;
            #define out(x) (cout<<#x<<": "<<x<<endl)
            const int maxint=0x7FFFFFFF;
            const long long maxlonglong=0x7FFFFFFFFFFFFFFFLL;
            template
            <class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
            template
            <class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}

            #define EPS 1e-10
            #define MaxN 3001

            struct point
            {
                
            double x, y;
            }
            ;

            struct cp
            {
                
            int n;
                point p[MaxN];
            }
            ;

            point intersectL(
            double a1, double b1, double c1, double a2, double b2, double c2)
            {
                point ret;
                ret.y 
            = (a1 * c2 - c1 * a2) / (b1 * a2 - a1 * b2);
                
            if (fabs(a2) < EPS)
                    ret.x 
            = -(b1 * ret.y + c1) / a1;
                
            else
                    ret.x 
            = -(b2 * ret.y + c2) / a2;
                
            return ret;
            }


            bool isEqual(point inpA, point inpB)
            {
                
            return (fabs(inpA.x - inpB.x) < EPS && fabs(inpA.y - inpB.y) < EPS);
            }


            double Cross(point inpA, point inpB, point inpC)
            {
                
            return (inpB.x - inpA.x) * (inpC.y - inpA.y) - (inpC.x - inpA.x) * (inpB.y - inpA.y);
            }


            void Get_line(point inpA, point inpB, double &a1, double &b1, double &c1)
            {
                a1 
            = inpB.y - inpA.y;
                b1 
            = inpA.x - inpB.x;
                c1 
            = inpA.y * (inpB.x - inpA.x) - inpA.x * (inpB.y - inpA.y);
            }


            cp cut(point inpA, point inpB, cp incp)
            {
                cp ret;
                point cross;
                
            int i, j;
                
            double t1, t2;
                
            double a1, b1, c1, a2, b2, c2;
                
                ret.n 
            = 0;
                
            for (i = 0; i < incp.n; i++)
                
            {
                    j 
            = i + 1;
                    t1 
            = Cross(inpA, inpB, incp.p[i]);
                    t2 
            = Cross(inpA, inpB, incp.p[j]);
                    
            if (t1 < EPS && t2 < EPS)
                    
            {
                        ret.p[ret.n
            ++= incp.p[i];
                        ret.p[ret.n
            ++= incp.p[j];
                    }

                    
            else if (t1 > EPS && t2 > EPS)
                        
            continue;
                    
            else
                    
            {
                        Get_line(inpA, inpB, a1, b1, c1);
                        Get_line(incp.p[i], incp.p[j], a2, b2, c2);
                        cross 
            = intersectL(a1, b1, c1, a2, b2, c2);
                        
                        
            if (t1 < EPS)
                        
            {
                            ret.p[ret.n
            ++= incp.p[i];
                            ret.p[ret.n
            ++= cross;
                        }

                        
            else
                        
            {
                            ret.p[ret.n
            ++= cross;
                            ret.p[ret.n
            ++= incp.p[j];
                        }

                    }

                }

                
            if (ret.n == 0return ret;
                
                
            for (i = 1, j = 1; i < ret.n; i++)
                    
            if (!isEqual(ret.p[i - 1], ret.p[i]))
                        ret.p[j
            ++= ret.p[i];

                ret.n 
            = j;
                
            if (ret.n != 1 && isEqual(ret.p[ret.n - 1], ret.p[0])) ret.n--;
                ret.p[ret.n] 
            = ret.p[0];
                
            return ret;
            }


            int main()
            {
                
            int ca;
                
            int n;
                cp input, ret;
                
            for (scanf("%d"&ca); ca--;)
                
            {
                    scanf(
            "%d"&n);
                    input.n 
            = n;
                    
            for (int i = 0; i < n; i++)
                        scanf(
            "%lf%lf"&input.p[i].x, &input.p[i].y);
                    input.p[input.n] 
            = input.p[0];
                    
                    ret 
            = input;
                    
            for (int i = 0; i < input.n; i++)
                        ret 
            = cut(input.p[i], input.p[i + 1], ret);
                    
            if (ret.n >= 1) printf("YES\n");
                    
            else printf("NO\n");
                }

                
            return 0;
            }
            posted on 2007-08-14 19:29 Felicia 閱讀(501) 評論(0)  編輯 收藏 引用 所屬分類: 計算幾何
             
            久久久久久久亚洲Av无码| 久久久久成人精品无码中文字幕| 久久午夜电影网| 91久久成人免费| 久久久精品久久久久影院| 亚洲va国产va天堂va久久| 久久精品国产亚洲综合色| 久久久久国产一区二区三区| 99久久无色码中文字幕人妻| 久久w5ww成w人免费| 日日狠狠久久偷偷色综合96蜜桃| 伊人久久大香线蕉av不变影院| 久久91精品国产91久久户| 日韩欧美亚洲综合久久影院Ds| 久久国产精品77777| 少妇被又大又粗又爽毛片久久黑人| 亚洲精品蜜桃久久久久久| 久久久综合香蕉尹人综合网| 久久婷婷五月综合国产尤物app| 久久九九久精品国产免费直播| 青青草原精品99久久精品66| 日本加勒比久久精品| 久久久久久免费一区二区三区| 久久人做人爽一区二区三区| 久久久久久A亚洲欧洲AV冫| 狠狠干狠狠久久| 欧美午夜精品久久久久免费视| 久久综合色区| 久久国产精品免费| 久久精品草草草| 久久国产精品99久久久久久老狼 | 国内精品久久国产大陆| 精品久久久久久国产| 人人狠狠综合88综合久久| 欧美性大战久久久久久| 久久国产精品国语对白| 久久久久亚洲精品天堂久久久久久| 久久国产精品久久国产精品| 99久久精品影院老鸭窝| 精品久久久久久无码专区不卡| 色欲久久久天天天综合网|