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

            poj 1265 Area

               此題用到了幾個(gè)知識(shí),一個(gè)是求多邊形面積的公式。然后是,根據(jù)頂點(diǎn)都在整點(diǎn)上求多邊形邊界上的頂點(diǎn)數(shù)目的方法。最后一個(gè)是pick
            定理。根據(jù)前面2個(gè)信息和pick定理算出在多邊形內(nèi)部的整點(diǎn)的個(gè)數(shù)。
               求多邊形面積的方法還是叉積代表有向面積的原理,把原點(diǎn)看做另外的一個(gè)點(diǎn)去分割原來的多邊形為N個(gè)三角形,然后把它們的有向面
            積加起來。
               判斷邊界上點(diǎn)的個(gè)數(shù)是根據(jù)Gcd(dx,dy)代表當(dāng)前邊上整數(shù)點(diǎn)的個(gè)數(shù)的結(jié)論。這個(gè)結(jié)論的證明其實(shí)也比較簡單,假設(shè)dx = a,dy = b。
            初始點(diǎn)是x0,y0,假設(shè)d = Gcd(a,b)。那么邊上的點(diǎn)可以被表示為(x0 + k * (a / d),y0 + k * (b / d))。為了使點(diǎn)是整數(shù)點(diǎn),
            k必須是整數(shù),而且0<= k <=d,所以最多有d個(gè)這個(gè)的點(diǎn)。
               求多邊形內(nèi)部點(diǎn)的個(gè)數(shù)用的是pick定理。面積 = 內(nèi)部點(diǎn) + 邊界點(diǎn) / 2 - 1。
               
               代碼如下:
            #include <stdio.h>
            #include <string.h>
            #include <algorithm>
            #include <math.h>
            using namespace std;
            #define MAX (100 + 10)

            struct Point
            {
                double x, y;
            };
            Point pts[MAX];

            int nN;
            const int IN = 1;
            const int EAGE = 2;
            const int OUT = 3;
            const double fPre = 1e-8;

            double Det(double fX1, double fY1, double fX2, double fY2)
            {
                return fX1 * fY2 - fX2 * fY1;
            }

            double Cross(Point a, Point b, Point c)
            {
                return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
            }

            double GetArea()
            {
                double fArea = 0.0;
                Point ori = {0.0, 0.0};

                for (int i = 0; i < nN; ++i)
                {
                    fArea += Cross(ori, pts[i], pts[(i + 1) % nN]);
                }
                return fabs(fArea) * 0.5;
            }

            int gcd(int nX, int nY)
            {
                if (nX < 0)
                {
                    nX = -nX;
                }
                if (nY < 0)
                {
                    nY = -nY;
                }
                if (nX < nY)
                {
                    swap(nX, nY);
                }
                while (nY)
                {
                    int nT = nY;
                    nY = nX % nY;
                    nX = nT;
                }
                return nX;
            }

            int main()
            {
                int nT;
                int nI, nE;
                double fArea;

                scanf("%d", &nT);
                int dx ,dy;
                
                for (int i = 1; i <= nT; ++i)
                {
                    scanf("%d", &nN);
                    nI = nE = 0;
                    pts[0].x = pts[0].y = 0;
                    for (int j = 1; j <= nN; ++j)
                    {
                        scanf("%d%d", &dx, &dy);
                        pts[j].x = pts[j - 1].x + dx;
                        pts[j].y = pts[j - 1].y + dy;
                        nE += gcd(dx, dy);
                    }
                    fArea = GetArea();
                    nI = (fArea + 1) - nE / 2;
                    printf("Scenario #%d:\n%d %d %.1f\n\n", i, nI, nE, fArea);
                }

                return 0;
            }

            posted on 2012-07-20 15:36 yx 閱讀(1045) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 計(jì)算幾何

            <2012年7月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導(dǎo)航

            統(tǒng)計(jì)

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學(xué)

            網(wǎng)友

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            色综合久久中文字幕无码| 麻豆精品久久久一区二区| 亚洲国产精品狼友中文久久久| 亚洲国产精品成人AV无码久久综合影院| 精品免费久久久久国产一区| 亚洲日韩欧美一区久久久久我| 老色鬼久久亚洲AV综合| 热re99久久精品国产99热| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 日本久久久精品中文字幕| 久久一区二区免费播放| 精品永久久福利一区二区| 久久久久亚洲av毛片大| 国产成年无码久久久久毛片| 国产亚洲精久久久久久无码AV| 久久久久久久久久久| 国产成人香蕉久久久久| 色欲综合久久躁天天躁蜜桃| 精品久久久久久久久久中文字幕| 伊人久久综合无码成人网| 久久精品一区二区三区中文字幕 | 国产精品禁18久久久夂久 | 国内精品久久久久影院网站 | 久久精品国产亚洲av水果派| 亚洲国产综合久久天堂| segui久久国产精品| 国产成人久久精品一区二区三区| 精品伊人久久久| 亚洲综合久久久| 亚洲?V乱码久久精品蜜桃| 久久精品国产黑森林| 国内精品久久久久久久久电影网 | 亚洲欧美国产精品专区久久| 国产99久久久国产精品~~牛| 国内精品久久久久久久97牛牛| 久久丫精品国产亚洲av不卡| 亚洲精品国产美女久久久| 久久久久久久97| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 亚洲国产成人久久一区WWW| 一本久道久久综合狠狠躁AV|