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

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



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

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

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

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

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

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

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

的實(shí)現(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 飛飛 閱讀(1315) 評論(3)  編輯 收藏 引用 所屬分類: ACM/ICPC

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

寫的不錯(cuò)啊!!!  回復(fù)  更多評論
  
# re: POJ 2335 浮點(diǎn)數(shù)的gcd
2008-12-04 23:44 | yumi
敬愛的……都不更新了  回復(fù)  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            性一交一乱一区二区洋洋av| 亚洲精品国久久99热| 亚洲一区二区三区四区五区黄| 欧美韩日一区二区| 日韩一区二区福利| 日韩一级免费观看| 国产日韩成人精品| 美女视频一区免费观看| 欧美1区2区视频| 亚洲永久网站| 久久精品理论片| 最新国产成人在线观看| 一本色道久久综合狠狠躁篇的优点| 欧美午夜激情在线| 久久亚洲私人国产精品va媚药| 美女网站久久| 羞羞漫画18久久大片| 久久久久久尹人网香蕉| 一区二区欧美激情| 久久久噜噜噜久久久| 日韩亚洲一区在线播放| 欧美在线1区| 99精品福利视频| 欧美一区免费视频| 99综合精品| 久久精品国产亚洲aⅴ| 一区二区三区日韩精品| 久久久免费精品视频| 亚洲欧美日本伦理| 欧美超级免费视 在线| 久久成人免费网| 欧美日韩亚洲国产精品| 久久久五月婷婷| 国产精品久久一区二区三区| 欧美激情导航| 国产精品视频大全| 日韩一级大片| 日韩天堂在线观看| 久久久夜精品| 久久久视频精品| 国产精品一区二区三区观看| 亚洲美女网站| 亚洲精品视频在线观看免费| 久久精品九九| 久久久久久噜噜噜久久久精品| 欧美午夜片在线免费观看| 亚洲第一搞黄网站| 亚洲电影欧美电影有声小说| 欧美一区二区三区视频在线观看| 一区二区三区日韩欧美| 欧美精品亚洲精品| 欧美激情免费在线| 亚洲国产毛片完整版| 久久人人超碰| 久久伊人免费视频| 黄色小说综合网站| 欧美一区二区三区四区在线| 久久精品理论片| 国产丝袜美腿一区二区三区| 欧美亚洲三级| 久久一区视频| 亚洲黄色视屏| 欧美a级理论片| 最新中文字幕一区二区三区| 99精品欧美一区| 欧美精品系列| 亚洲五月六月| 欧美一区二区大片| 国产亚洲欧美日韩日本| 欧美一区午夜视频在线观看| 欧美一区日韩一区| 国产日韩亚洲欧美精品| 久久国产精品亚洲77777| 久久久不卡网国产精品一区| 国产精品视频大全| 欧美在线观看视频一区二区三区| 久久免费精品视频| 亚洲国产精品123| 欧美日韩精品在线| 亚洲欧美色一区| 久久综合给合久久狠狠色| 亚洲国产成人tv| 欧美精品日韩| 午夜激情综合网| 免费久久99精品国产| 99热免费精品在线观看| 国产精品乱码妇女bbbb| 亚洲欧洲99久久| 免费日韩av电影| 亚洲色图自拍| 国内自拍亚洲| 欧美日韩在线免费视频| 久久高清一区| 亚洲美女毛片| 欧美 日韩 国产精品免费观看| 欧美国产日产韩国视频| 亚洲欧美国产高清| 国产一区自拍视频| 欧美日韩高清一区| 亚洲欧美三级伦理| 亚洲激情精品| 久久精品国产91精品亚洲| 亚洲人成在线观看网站高清| 国产乱码精品一区二区三区av| 久久乐国产精品| 制服丝袜亚洲播放| 欧美高清视频一区二区三区在线观看| 亚洲色图在线视频| 亚洲国产精品久久久久| 国产精品一区久久| 欧美巨乳在线观看| 久热re这里精品视频在线6| 亚洲一本视频| 亚洲精品老司机| 免费观看亚洲视频大全| 久久精品国产成人| 亚洲伊人伊色伊影伊综合网| 91久久综合| 国产综合色在线| 国产伦精品一区二区三区高清版 | 午夜精品视频网站| 亚洲国产精品va在线看黑人动漫| 欧美亚洲成人免费| 欧美精品日韩| 欧美精品国产| 欧美国产日韩免费| 蜜桃久久av| 久久午夜电影网| 欧美在线观看视频在线| 午夜亚洲伦理| 午夜性色一区二区三区免费视频| 亚洲精品一区二区三区婷婷月 | 亚洲视频一二| 亚洲特级片在线| 一区二区免费在线播放| 亚洲精品欧洲| 伊人成年综合电影网| 国内揄拍国内精品久久| 黄色亚洲精品| 在线日韩av片| 亚洲黄网站在线观看| 亚洲激情在线观看| 日韩一级免费观看| 亚洲私拍自拍| 亚洲欧美综合另类中字| 欧美一级片久久久久久久| 午夜精品久久久| 欧美在线欧美在线| 久久午夜电影网| 欧美国产成人在线| 亚洲国产另类精品专区| 亚洲免费播放| 亚洲欧美精品| 久久久777| 欧美精品在线免费| 国产精品国产a| 国内精品久久国产| 亚洲电影免费观看高清完整版在线| 最新日韩在线视频| 99xxxx成人网| 亚洲欧美在线免费| 久久这里有精品视频| 欧美成人官网二区| av成人天堂| 亚洲欧美日韩一区二区三区在线观看 | 欧美成人午夜激情视频| 亚洲精品视频在线观看网站| 一本色道久久综合狠狠躁的推荐| 性做久久久久久久久| 免费在线看成人av| 国产精品欧美风情| 亚洲国产精品成人精品| 中文亚洲欧美| 久久综合狠狠| 一区二区三区高清| 久久午夜国产精品| 国产精品美女www爽爽爽视频| 韩日精品在线| 亚洲午夜未删减在线观看| 久久这里有精品视频| 一本色道久久综合精品竹菊| 久久免费视频一区| 国产精品一区二区久久久久| 亚洲精品123区| 久久精品综合一区| 日韩午夜在线视频| 玖玖综合伊人| 国产欧美日韩中文字幕在线| 日韩午夜电影| 另类激情亚洲| 午夜精品偷拍| 国产精品久线观看视频| 亚洲伦理久久| 免费亚洲视频| 欧美有码视频| 国产乱码精品一区二区三区五月婷| 日韩视频免费看| 欧美不卡视频一区| 久久国产黑丝| 国产一区二区三区四区三区四|