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

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>
            亚洲黄色影片| 今天的高清视频免费播放成人| 国产一区二区av| 久久久噜噜噜久久久| 欧美亚洲午夜视频在线观看| 国产午夜精品麻豆| 裸体女人亚洲精品一区| 欧美成人第一页| 亚洲综合色丁香婷婷六月图片| 亚洲欧美国产精品桃花| 伊人久久婷婷| 日韩性生活视频| 国产欧美一区二区精品秋霞影院 | 欧美电影美腿模特1979在线看| 亚洲乱码国产乱码精品精 | 欧美在线视频播放| 久久亚洲综合色| 亚洲图片激情小说| 久久精品日韩| 亚洲主播在线观看| 久久亚洲一区二区| 亚洲免费人成在线视频观看| 久久精品国产久精国产思思| 一本色道久久| 久久久国产视频91| 亚洲在线成人| 男人插女人欧美| 久久国产精品亚洲va麻豆| 你懂的成人av| 久久精品视频一| 欧美日韩国产成人在线| 久久综合九色综合欧美就去吻| 欧美理论电影在线播放| 久久全国免费视频| 国产精品久久久久久户外露出| 欧美.com| 国产亚洲精品综合一区91| 亚洲精品影视| 亚洲剧情一区二区| 麻豆精品网站| 久久影院亚洲| 国产原创一区二区| 亚洲欧美国产一区二区三区| 在线亚洲欧美视频| 女女同性精品视频| 另类av导航| 国产在线视频欧美一区二区三区| 日韩视频在线观看| 亚洲精品一区二| 麻豆av福利av久久av| 久久综合色天天久久综合图片| 国产精品无码专区在线观看| 日韩亚洲在线观看| 在线一区视频| 欧美日韩在线观看视频| 亚洲三级影片| 一本色道久久88精品综合| 欧美成人精品在线观看| 欧美不卡视频一区发布| 在线不卡视频| 美女啪啪无遮挡免费久久网站| 免费在线观看精品| 在线成人av网站| 老牛嫩草一区二区三区日本| 欧美~级网站不卡| 亚洲国语精品自产拍在线观看| 久久夜色精品国产| 欧美激情亚洲综合一区| 亚洲国产精品悠悠久久琪琪| 女同一区二区| 亚洲精品在线三区| 亚洲欧美文学| 国内外成人免费视频| 久久久国产午夜精品| 欧美高清在线观看| 野花国产精品入口| 国产精品久久久久一区二区三区| 一区二区三区你懂的| 午夜精品一区二区三区电影天堂| 国产日韩一区二区三区在线| 久久国内精品自在自线400部| 女女同性女同一区二区三区91| 亚洲国产一区二区三区青草影视| 欧美激情第1页| 在线视频欧美精品| 久久综合色综合88| 99re热精品| 国产伦精品一区二区三区视频黑人 | 亚洲福利免费| 欧美日韩另类在线| 午夜精品久久一牛影视| 另类春色校园亚洲| 一区二区三区欧美视频| 国产欧美日本一区二区三区| 狼人社综合社区| 亚洲视频图片小说| 亚洲第一伊人| 欧美淫片网站| 99国产精品99久久久久久| 国产九九视频一区二区三区| 美女在线一区二区| 亚洲欧美在线观看| 亚洲黄色在线| 久久久久一区二区三区四区| 亚洲视频电影图片偷拍一区| 精品粉嫩aⅴ一区二区三区四区| 欧美日韩第一区日日骚| 久久精品二区| 亚洲一区日本| 亚洲三级影院| 美国十次了思思久久精品导航| 亚洲无线视频| 亚洲精品专区| 亚洲国产成人在线视频| 国产欧美精品一区二区三区介绍| 欧美精品v国产精品v日韩精品 | 亚洲欧洲日产国码二区| 久久亚洲精品网站| 欧美影院成人| 国产精品家庭影院| 亚洲人精品午夜在线观看| 欧美日韩系列| 亚洲一区日本| 99视频精品| 亚洲国产精品一区二区第一页 | 久久久国产精品亚洲一区| 国产精品99久久久久久久女警| 91久久精品一区二区别| 韩国在线视频一区| 国产一区二区剧情av在线| 国产精品免费区二区三区观看| 欧美日韩精品一区二区三区| 欧美成人午夜免费视在线看片| 久久精品av麻豆的观看方式| 亚洲欧美精品suv| 亚洲欧美在线磁力| 亚洲欧美高清| 欧美亚洲视频在线观看| 欧美一区二区三区免费观看| 香蕉免费一区二区三区在线观看 | 久久精品人人做人人综合| 欧美一区午夜视频在线观看| 欧美在线视频播放| 欧美伊人久久大香线蕉综合69| 亚洲免费视频一区二区| 亚洲欧美中文另类| 久久国产视频网| 久久精品一区二区| 噜噜噜噜噜久久久久久91| 欧美α欧美αv大片| 欧美成人在线免费观看| 欧美精品三级在线观看| 欧美日韩一区二区三区在线观看免| 欧美日韩三级| 国产嫩草影院久久久久| 黄色av成人| 亚洲精品午夜| 午夜精品久久久久久| 久久黄色影院| 欧美黄色aaaa| 一区二区三区四区国产| 亚洲专区一区二区三区| 久久久国产一区二区| 免费一级欧美在线大片| 欧美日韩一区二区三| 国产精品日韩一区| 亚洲动漫精品| 亚洲视频1区| 久久色在线播放| 亚洲欧洲一区二区在线播放| 亚洲天堂成人在线视频| 久久久久网站| 国产精品av一区二区| 红桃av永久久久| 亚洲午夜羞羞片| 久久综合狠狠综合久久综合88 | 牛夜精品久久久久久久99黑人| 亚洲看片一区| 久久精品国产一区二区三| 欧美日本精品一区二区三区| 国产深夜精品| 一区二区三区毛片| 狂野欧美性猛交xxxx巴西| 日韩网站在线看片你懂的| 久久精品视频99| 国产精品免费一区二区三区观看| 国内精品久久久久影院薰衣草 | 黄色成人91| 午夜精品久久久久久久| 欧美成熟视频| 欧美淫片网站| 国产精品久久久久99| 亚洲欧洲一区二区三区| 久久精品综合| 99精品热视频只有精品10| 久久久久这里只有精品| 国产精品久久久久影院色老大| 亚洲精品少妇| 欧美韩国日本一区| 久久久久国产一区二区三区四区 |