• <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>
            alpc60 ACM/ICPC程序設(shè)計
            成長的路……源
            posts - 20,comments - 42,trackbacks - 0
            Temple of Dune
            Time Limit: 1000MS Memory Limit: 65536K
            Total Submissions: 211 Accepted: 82

            Description

            The Archaeologists of the Current Millenium (ACM) now and then discover ancient artifacts located at the vertices of regular polygons. In general it is necessary to move one sand dune to uncover each artifact. After discovering three artifacts, the archaeologists wish to compute the minimum number of dunes that must be moved to uncover all of them.

            Input

            The first line of input contains a positive integer n, the number of test cases. Each test case consists of three pairs of real numbers giving the x and y coordinates of three vertices from a regular polygon.

            Output

            For each line of input, output a single integer stating the fewest vertices that such a polygon might have. You may assume that each input case gives three distinct vertices of a regular polygon with at most 200 vertices.

            Sample Input

            4
            10.00000 0.00000 0.00000 -10.00000 -10.00000 0.00000
            22.23086 0.42320 -4.87328 11.92822 1.76914 27.57680
            156.71567 -13.63236 139.03195 -22.04236 137.96925 -11.70517
            129.400249 -44.695226 122.278798 -53.696996 44.828427 -83.507917
            

            Sample Output

            4
            6
            23
            100
            

            Source



            題目大意是給出三個點的(x,y)坐標(biāo),要求輸出一個邊數(shù)最小的正多邊形的邊數(shù),使這三個點恰好在

            這個正多邊形上面。其實這個三角形和這個正多邊形是共外接圓,由外接圓的圓心出發(fā),三角形的三

            條邊可以把圓分成三份,每份圓弧所對應(yīng)的圓心角分別為arg[0],arg[1]和arg[2],正多邊形把圓弧

            分成相等的n份,每份對應(yīng)的圓心角為2*pi/n。其實三角形的三個角就分別占用了若干等份正多邊形

            所劃分的圓弧,最后也就只要求arg[0],arg[1],arg[2]和2*pi的最大公約數(shù)(gcd)即可。但是這里是

            個角度都是浮點數(shù),所以還定義一個浮點數(shù)的gcd,計算浮點數(shù)的gcd可以利用math.h的函數(shù)fmod

            (x,y)表示x%y。例如3.5%0.3=0.2,x%y的結(jié)果為不超過y的一個浮點數(shù)。下面寫了一個fmod(x,y)自己

            的實現(xiàn)。
            double fmod(double x, double y)
            {
             return x-floor(x/y)*y;
            }
            有了fmod函數(shù)以后,就可以用它來求gcd了!
            double fgcd(double a, double b)
            {
             double t;
             if(dblcmp(a-b) == 1)  //a>b
             {
              t=a;
              a=b;
              b=t;
             }
             if(dblcmp(a) == 0) return b;
             return fgcd(fmod(b,a),a);
            }

            posted on 2008-06-28 15:18 飛飛 閱讀(1298) 評論(3)  編輯 收藏 引用 所屬分類: ACM/ICPC

            FeedBack:
            # re: POJ 2335 浮點數(shù)的gcd
            2008-08-16 04:56 | ecnu_zp
            果然能從alpc大牛這里學(xué)到東東。。。(*^__^*) 嘻嘻……  回復(fù)  更多評論
              
            # re: POJ 2335 浮點數(shù)的gcd
            2008-11-24 23:06 | 11
            大牛啊。。最近我都在學(xué)習(xí)你的blog呢。。。

            寫的不錯啊!!!  回復(fù)  更多評論
              
            # re: POJ 2335 浮點數(shù)的gcd
            2008-12-04 23:44 | yumi
            敬愛的……都不更新了  回復(fù)  更多評論
              
            国产亚洲婷婷香蕉久久精品| 亚洲国产一成久久精品国产成人综合 | 伊人久久大香线蕉综合热线| 亚洲国产成人久久精品99 | 日韩中文久久| 亚洲AV日韩AV天堂久久| 91精品免费久久久久久久久| 中文精品久久久久人妻| 无码国产69精品久久久久网站| 精品久久久久久久| 亚洲国产小视频精品久久久三级| 久久精品人成免费| 欧美国产精品久久高清| 99久久国语露脸精品国产| 久久无码专区国产精品发布| 狠狠色噜噜狠狠狠狠狠色综合久久| 一级a性色生活片久久无| 久久福利青草精品资源站免费| 欧美性猛交xxxx免费看久久久| 国产亚洲综合久久系列| 久久人妻少妇嫩草AV蜜桃| 7国产欧美日韩综合天堂中文久久久久 | 色综合久久88色综合天天 | 久久精品一区二区三区不卡| 国产A三级久久精品| 狠狠综合久久综合中文88| 久久91精品国产91久久户| 国产毛片欧美毛片久久久| 久久噜噜久久久精品66| 国产精品内射久久久久欢欢| 国产精品久久久亚洲| 色狠狠久久AV五月综合| 国产色综合久久无码有码| 久久精品免费一区二区| 久久久久久精品久久久久| 久久亚洲熟女cc98cm| 午夜不卡久久精品无码免费| 伊人久久大香线蕉AV色婷婷色| 久久久这里只有精品加勒比| 怡红院日本一道日本久久| 久久国产成人午夜aⅴ影院|