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

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 飛飛 閱讀(1315) 評論(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ù)  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美—级高清免费播放| 亚洲免费在线播放| 欧美v国产在线一区二区三区| 新狼窝色av性久久久久久| 国产九九精品| 久久亚洲一区二区三区四区| 欧美在线一二三| 亚洲国产视频一区| 亚洲乱码日产精品bd| 国产精品免费网站| 麻豆freexxxx性91精品| 欧美激情一区二区三区 | 久久成人精品视频| 一区在线观看| 99re6这里只有精品| 国产欧美在线观看| 亚洲福利一区| 欧美精品一区二区三区很污很色的 | 国产精品一区二区在线观看| 久久男女视频| 欧美理论电影在线播放| 欧美在线精品免播放器视频| 久久伊人亚洲| 亚洲男人的天堂在线aⅴ视频| 久久精品免费电影| 亚洲无限av看| 久久久精品动漫| 亚洲在线成人精品| 牛牛影视久久网| 欧美中文字幕视频| 欧美日本免费| 老司机成人在线视频| 欧美视频成人| 亚洲丰满少妇videoshd| 国产欧美精品在线播放| 亚洲欧洲日本在线| 激情久久中文字幕| 亚洲午夜羞羞片| 日韩午夜激情av| 国产精品99一区二区| 亚洲欧美网站| 欧美精品日韩一本| 免费观看在线综合色| 国产欧美日韩另类一区 | 亚洲综合精品| 欧美激情日韩| 免费看精品久久片| 国产欧美一区二区色老头| 99re这里只有精品6| 亚洲国产精品久久人人爱蜜臀 | 一本久久精品一区二区| 91久久精品国产91久久性色tv | 日韩视频在线观看| 亚洲日本va在线观看| 欧美中文字幕视频在线观看| 亚洲欧美综合v| 欧美视频在线免费看| 亚洲激情网址| 亚洲日本电影在线| 免费观看30秒视频久久| 久久人人爽爽爽人久久久| 国产亚洲欧洲一区高清在线观看 | 9国产精品视频| 9l国产精品久久久久麻豆| 欧美不卡视频一区发布| 亚洲第一精品福利| 亚洲精品极品| 欧美人与性禽动交情品| 亚洲精品一区二区三区福利| 日韩天堂在线视频| 欧美日韩在线视频一区| 99re亚洲国产精品| 欧美一区二区三区喷汁尤物| 国产情侣一区| 久久免费一区| 亚洲久久视频| 亚洲免费一区二区| 国产精品入口日韩视频大尺度| 亚洲性图久久| 久久九九热re6这里有精品| 狠狠色丁香婷婷综合| 久久精品夜色噜噜亚洲aⅴ| 免费视频亚洲| 一本一本久久a久久精品综合麻豆 一本一本久久a久久精品牛牛影视 | 在线不卡免费欧美| 免费成年人欧美视频| 亚洲承认在线| 亚洲一区在线免费| 韩日视频一区| 欧美成人精品1314www| 一本色道久久综合亚洲91| 新狼窝色av性久久久久久| 国产日韩免费| 美女日韩欧美| 在线亚洲一区| 美日韩免费视频| 亚洲午夜国产成人av电影男同| 国产精品欧美久久久久无广告| 欧美一区二区大片| 91久久精品一区| 欧美一区免费| 亚洲精品欧美专区| 国产欧美精品日韩精品| 久久色在线播放| 中日韩高清电影网| 欧美77777| 午夜视频一区在线观看| 亚洲国产精品久久久久秋霞影院| 欧美日韩中文字幕日韩欧美| 羞羞漫画18久久大片| 亚洲人成网站精品片在线观看| 欧美在线看片a免费观看| 亚洲欧洲一二三| 国产日韩欧美综合| 欧美日韩亚洲视频| 免费久久精品视频| 欧美亚洲视频在线看网址| 亚洲精品网站在线播放gif| 久久乐国产精品| 亚洲女与黑人做爰| 亚洲狼人综合| 影音先锋欧美精品| 国产精品视频在线观看| 欧美日本韩国一区二区三区| 久久久久九九九九| 羞羞色国产精品| 亚洲综合视频1区| 日韩一二三在线视频播| 亚洲国产精品成人一区二区| 久色婷婷小香蕉久久| 久久精品91久久久久久再现| 亚洲一区国产| 亚洲小少妇裸体bbw| 99精品福利视频| 亚洲精品一区中文| 亚洲国产成人av| 亚洲国产视频一区二区| 亚洲高清色综合| 亚洲高清视频一区二区| 在线播放视频一区| 在线欧美日韩| 亚洲黄色小视频| 亚洲人成亚洲人成在线观看图片| 狠狠色丁香久久婷婷综合丁香| 国产欧美一区二区三区沐欲 | 国产精品久久一卡二卡| 国产精品久久久久久久久久三级 | 国产精品综合| 国内成人精品视频| 亚洲国产91精品在线观看| 亚洲国产精品久久久久婷婷老年| 亚洲国产成人高清精品| 亚洲人成亚洲人成在线观看| 日韩一区二区精品视频| 亚洲视频二区| 性欧美大战久久久久久久久| 久久精品国产精品亚洲| 久久天堂av综合合色| 欧美激情1区2区3区| 日韩一级大片| 欧美主播一区二区三区| 久久综合久色欧美综合狠狠 | 国产精品日韩一区二区| 国产自产2019最新不卡| 最新国产成人在线观看| 宅男精品视频| 久久国产主播| 亚洲国产精品一区制服丝袜| 一区二区日韩| 久久久999精品| 欧美精品免费播放| 国产精品久久久久久久午夜| 欧美77777| 亚洲精选大片| 亚洲女ⅴideoshd黑人| 欧美激情第六页| 亚洲第一天堂av| 免费欧美在线视频| 亚洲图片在线| 久久人人爽人人| 久久综合九色九九| 亚洲青色在线| 亚洲激情第一区| 亚洲伊人伊色伊影伊综合网 | 正在播放亚洲一区| 麻豆精品国产91久久久久久| 99在线精品观看| 久久久亚洲欧洲日产国码αv| 欧美日韩一区不卡| 在线观看欧美| 久久国产66| 9久re热视频在线精品| 欧美一区日本一区韩国一区| 欧美激情一区二区三区四区 | 欧美有码视频| 欧美日韩免费看| 亚洲日本激情| 欧美a级在线| 亚洲女人av| 欧美一区二区三区四区在线观看|