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

            PKU 1265 Area---計算幾何

            Posted on 2009-10-02 03:01 Uriel 閱讀(206) 評論(0)  編輯 收藏 引用 所屬分類: POJ計算幾何

            求頂點為整數的任意多邊形內部整點數(Pick定理),邊上整點數(GCD),面積(叉積)

            第一次知道Pick定理。。
            注意。。叉積求出面積可能是負數,需要處理下
            /*Problem: 1265  User: Uriel 
               Memory: 172K  Time: 16MS 
               Language: C++  Result: Accepted
            */


            #include
            <math.h>
            #include
            <stdio.h>
            #include
            <stdlib.h>
            #define MAXN 110
            #define ABS(x) (x<0?-x:x)
            struct point
            {
                
            int x,y;    
            }
            ;

            point P[MAXN],T;

            int t,n,i,EPoint,IPoint,Asum;

            int cross_product(point a,point b)
            {
                
            return a.x*b.y-a.y*b.x;
            }


            int GCD(int x,int y)
            {
                
            if(y==0)return x;
                
            else
                    
            return GCD(y,x%y);
            }


            int main()
            {
                scanf(
            "%d",&t);
                
            for(int i=1;i<=t;i++)
                
            {
                    scanf(
            "%d",&n);
                    Asum
            =0;
                    EPoint
            =0;
                    P[
            0].x=0;
                    P[
            0].y=0;
                    
            for(int j=1;j<=n;j++)
                    
            {
                        scanf(
            "%d %d",&T.x,&T.y);
                        P[j].x
            =P[j-1].x+T.x;
                        P[j].y
            =P[j-1].y+T.y;
                        EPoint
            +=GCD(ABS(T.x),ABS(T.y));
                        Asum
            +=cross_product(P[j-1],P[j]);
                    }

                    
            if(Asum<0)
                    
            {
                        Asum
            =-Asum;
                    }

                    IPoint
            =Asum/2+1-EPoint/2;
                    printf(
            "Scenario #%d:\n%d %d %.1f\n\n",i,IPoint,EPoint,((double)Asum)/2);
                }

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

            亚洲国产精品人久久| 性做久久久久久久| 久久综合成人网| 一本久道久久综合狠狠躁AV| 国产亚洲精久久久久久无码77777 国产亚洲精品久久久久秋霞 | 欧美日韩成人精品久久久免费看| 久久福利资源国产精品999| 久久精品a亚洲国产v高清不卡| 久久久久亚洲精品天堂久久久久久 | WWW婷婷AV久久久影片| 欧美性大战久久久久久| 国产69精品久久久久9999APGF| 久久亚洲精品视频| 99久久国产宗和精品1上映| 久久WWW免费人成—看片| 国产亚洲综合久久系列| 少妇熟女久久综合网色欲| 久久精品国产亚洲一区二区| 久久婷婷色综合一区二区| 99久久免费只有精品国产| 少妇内射兰兰久久| 久久综合久久美利坚合众国| 久久久久人妻一区精品果冻| 99久久精品国产高清一区二区| 亚洲午夜久久久久久久久电影网| 久久人人爽人人爽人人片AV麻豆| 国产高清国内精品福利99久久| 亚洲国产一成人久久精品| 亚洲天堂久久久| 久久综合给合综合久久| 久久青青草原精品国产不卡| 亚洲国产精品久久久久婷婷老年| 久久九九亚洲精品| 99久久人妻无码精品系列蜜桃| 亚洲AV日韩AV天堂久久| 亚洲AV无码久久精品成人 | 久久热这里只有精品在线观看| 热综合一本伊人久久精品| 色婷婷久久久SWAG精品| 无码任你躁久久久久久老妇App| 久久国产成人午夜aⅴ影院|