青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

alpc60 ACM/ICPC程序設計
成長的路……源
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)坐標,要求輸出一個邊數最小的正多邊形的邊數,使這三個點恰好在

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

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

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

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

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

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

的實現。
double fmod(double x, double y)
{
 return x-floor(x/y)*y;
}
有了fmod函數以后,就可以用它來求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 飛飛 閱讀(1315) 評論(3)  編輯 收藏 引用 所屬分類: ACM/ICPC

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

寫的不錯啊!!!  回復  更多評論
  
# re: POJ 2335 浮點數的gcd
2008-12-04 23:44 | yumi
敬愛的……都不更新了  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产日产欧美a一级在线| 久久久久久97三级| 欧美日韩视频在线第一区| 一本综合久久| 亚洲专区欧美专区| 国产亚洲精品aa| 欧美激情黄色片| 欧美精品一区二区三区视频 | 欧美一区二区三区免费观看 | 欧美日韩视频第一区| 亚洲午夜精品久久久久久浪潮| 中文av字幕一区| 国产喷白浆一区二区三区| 久久久在线视频| 欧美成人在线免费观看| 亚洲综合色丁香婷婷六月图片| 欧美一二三视频| 亚洲国产日韩在线一区模特| 一区二区三区欧美激情| 国产亚洲激情在线| 亚洲人成7777| 国产欧美一区二区三区久久| 欧美wwwwww| 国产精品久久二区二区| 久久久综合激的五月天| 欧美a级理论片| 欧美在线观看视频| 美女网站在线免费欧美精品| 亚洲女ⅴideoshd黑人| 久久嫩草精品久久久精品一| 亚洲免费一区二区| 欧美精品日韩www.p站| 狠狠干综合网| 亚洲精品在线电影| 狠狠色狠狠色综合日日tαg| 亚洲区免费影片| 国产视频自拍一区| 亚洲精品影视在线观看| 一区二区在线观看视频| 一区二区三区国产在线观看| 亚洲国产乱码最新视频| 午夜精品在线| 亚洲一区美女视频在线观看免费| 久久久久网站| 久久精品观看| 国产精品视频久久久| 亚洲人人精品| 午夜国产精品视频免费体验区| 先锋影音久久久| 亚洲一区二区黄| 99国产精品国产精品毛片| 国产精品伦子伦免费视频| 蜜桃久久精品一区二区| 国产欧美日韩一区二区三区在线观看| 亚洲精品一品区二品区三品区| 亚洲福利电影| 久久久综合激的五月天| 久久亚洲午夜电影| 国产亚洲成精品久久| 亚洲欧美日韩国产| 午夜伦欧美伦电影理论片| 欧美午夜在线一二页| 亚洲精品久久| 在线视频你懂得一区二区三区| 欧美经典一区二区| 亚洲精品极品| 一本大道久久a久久精二百| 欧美另类视频| av成人免费在线| 亚洲欧美制服另类日韩| 国产精品久久久久久久久久久久久久| 一区二区三区国产在线| 欧美一二三区精品| 国产主播精品在线| 久久久亚洲高清| 亚洲国产成人午夜在线一区 | 久久精品av麻豆的观看方式| 久久综合久久综合久久综合| 在线成人av| 麻豆91精品91久久久的内涵| 亚洲三级毛片| 亚洲欧美中文日韩在线| 国产亚洲欧美aaaa| 久久综合九色综合欧美就去吻| 亚洲国产精品热久久| 亚洲影视在线播放| 国产视频亚洲精品| 狂野欧美激情性xxxx欧美| 亚洲全部视频| 久久成人一区| 亚洲精品1234| 国产精品午夜视频| 老鸭窝毛片一区二区三区| 亚洲美女网站| 久久久国产91| 一区二区三区视频在线播放| 国产色产综合产在线视频| 欧美电影资源| 性欧美长视频| 日韩午夜精品| 麻豆久久久9性大片| 中国成人亚色综合网站| 国产在线视频欧美| 欧美日韩精品系列| 欧美影视一区| 99亚洲一区二区| 麻豆久久精品| 亚洲综合99| 亚洲精品视频在线观看网站 | 欧美国产91| 欧美一区免费视频| 一本色道久久精品| 欧美成人午夜激情在线| 亚洲一级片在线观看| 在线观看中文字幕不卡| 国产精品久久久久毛片软件| 免费av成人在线| 欧美一区久久| 亚洲制服少妇| 一区二区电影免费观看| 美女视频黄a大片欧美| 国产日韩精品一区二区三区| 欧美久久99| 老司机免费视频久久| 欧美亚洲一区二区在线观看| 一区二区激情| 99pao成人国产永久免费视频| 欧美国产综合视频| 农夫在线精品视频免费观看| 久久婷婷国产麻豆91天堂| 午夜精品免费在线| 亚洲影视在线| 亚洲欧美亚洲| 亚洲一区二区三区视频| 在线视频精品一区| 一区二区三区精品| 日韩一区二区精品| 99精品99| 日韩午夜在线视频| 99精品国产高清一区二区| 亚洲精品四区| 一区二区久久久久| 日韩午夜剧场| 亚洲午夜成aⅴ人片| 亚洲小说欧美另类婷婷| 亚洲一区二区三区精品视频| 制服诱惑一区二区| 亚洲欧美国产77777| 先锋a资源在线看亚洲| 亚洲欧美影院| 久久久99免费视频| 老司机aⅴ在线精品导航| 欧美成人xxx| 亚洲国产精品久久久久婷婷884 | 99视频有精品| 亚洲无线一线二线三线区别av| 亚洲欧美精品| 久久精品人人爽| 久久这里只有| 亚洲电影自拍| 一本色道久久综合亚洲精品不| 亚洲自拍偷拍一区| 久久人人爽爽爽人久久久| 欧美成人综合| 国产精品久久久久秋霞鲁丝 | 国产精品美女久久久久av超清 | 精品99视频| 亚洲精品乱码久久久久久蜜桃麻豆| 日韩一级免费观看| 亚洲一区精彩视频| 久久不射2019中文字幕| 免费亚洲电影| 一区二区三区视频观看| 久久福利精品| 欧美日韩视频专区在线播放| 国产日韩欧美高清| 亚洲免费av观看| 久久精品国产99精品国产亚洲性色| 欧美国产精品劲爆| 亚洲自拍16p| 免费在线观看日韩欧美| 国产乱码精品1区2区3区| 亚洲福利在线视频| 亚洲欧美韩国| 欧美韩日一区二区三区| 亚洲在线黄色| 欧美电影在线免费观看网站 | 久久精品视频在线看| 欧美激情亚洲综合一区| 国产欧美日韩三区| 亚洲精品一区二区在线| 久久九九久精品国产免费直播| 91久久极品少妇xxxxⅹ软件| 久久精品国产成人| 欧美日韩在线三级| 91久久国产综合久久蜜月精品 | 久久综合色婷婷| aa级大片欧美三级| 免费成人你懂的| 狠狠久久亚洲欧美专区|