• <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高清| 九九99精品久久久久久| 性做久久久久久免费观看| 国产成人精品久久| 狠狠人妻久久久久久综合| 99久久夜色精品国产网站| 久久99国产精品一区二区| 囯产极品美女高潮无套久久久| av无码久久久久久不卡网站| 亚洲日本va午夜中文字幕久久| 久久福利青草精品资源站| 无码AV中文字幕久久专区 | 久久精品国产2020| 亚洲国产精品久久| 久久精品国产亚洲av水果派| 中文精品久久久久人妻| 国产精品内射久久久久欢欢| 精品无码久久久久久尤物| 免费精品久久天干天干| 亚洲综合久久夜AV | 久久99精品国产99久久6| 99热成人精品热久久669| 色综合久久久久综合体桃花网 | 囯产精品久久久久久久久蜜桃 | 久久精品国产91久久综合麻豆自制 | 久久久久久亚洲精品不卡| 成人免费网站久久久| 日韩精品久久久久久久电影蜜臀 | 久久精品国产亚洲av影院| 伊人情人综合成人久久网小说| 国产精品青草久久久久福利99 | 久久久久久久波多野结衣高潮 | 久久精品国产亚洲AV嫖农村妇女| 伊人久久大香线蕉av不变影院| 久久精品国产精品亚洲精品| 麻豆成人久久精品二区三区免费| 亚洲精品乱码久久久久久按摩| 亚洲精品国精品久久99热一|