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

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>
            欧美激情综合色| 亚洲免费在线精品一区| 久久久久久噜噜噜久久久精品| 正在播放欧美一区| 国产欧美日本在线| 久久综合免费视频影院| 久久精品成人欧美大片古装| 国产亚洲女人久久久久毛片| 久久精品人人做人人爽| 久久亚洲精选| 这里只有精品在线播放| 亚洲欧美国产精品va在线观看| 国产精品国码视频| 久久深夜福利免费观看| 欧美电影免费观看网站| 亚洲一区二区三区影院| 久久不射中文字幕| 99re6热在线精品视频播放速度 | 国内精品视频久久| 欧美国产精品| 国产精品国产a级| 久久一区二区精品| 欧美日韩亚洲一区在线观看| 久久精品国产一区二区三区| 欧美精品成人| 久久久国产视频91| 欧美日韩在线影院| 久久综合影音| 国产精品av久久久久久麻豆网| 久久久免费观看视频| 欧美激情免费观看| 久久精品国内一区二区三区| 欧美精品在线观看一区二区| 欧美中文字幕在线| 欧美区一区二| 久久久噜噜噜久久久| 欧美视频第二页| 亚洲第一黄色网| 国产伦精品一区二区三区免费迷| 欧美国产精品中文字幕| 国产亚洲a∨片在线观看| 亚洲欧洲日产国产综合网| 激情久久婷婷| 亚洲免费影视第一页| 宅男在线国产精品| 欧美激情久久久久久| 快射av在线播放一区| 国产精品一区免费视频| 99国产精品久久久久老师| 亚洲激情网站| 久久久久久亚洲精品杨幂换脸| 午夜精品视频在线观看一区二区| 欧美福利一区二区| 模特精品裸拍一区| 伊人成综合网伊人222| 亚洲欧美一区二区三区在线 | 国产亚洲欧美一区在线观看| 宅男66日本亚洲欧美视频| 亚洲欧洲日本一区二区三区| 久久色在线观看| 久久亚洲一区二区| 国产精品亚洲成人| 亚洲一区二区在线视频| 亚洲午夜一区二区| 国产精品r级在线| 亚洲最新色图| 亚洲一区亚洲| 欧美亚韩一区| 亚洲视频在线观看| 欧美在线观看日本一区| 国产一二精品视频| 久久精品一区二区国产| 猛干欧美女孩| 亚洲精品综合精品自拍| 欧美久久一区| 亚洲午夜黄色| 久久亚洲综合网| 亚洲第一黄网| 欧美日韩精品免费观看| 亚洲一区高清| 欧美成人精品一区二区三区| 亚洲国产一区二区三区青草影视| 欧美va天堂在线| 9色精品在线| 亚洲一区二区三区视频| 国产欧美一区二区三区视频| 久久色在线观看| 亚洲免费播放| 久久偷窥视频| 中文在线资源观看网站视频免费不卡 | 91久久久精品| 午夜精彩视频在线观看不卡| 国产一区亚洲一区| 欧美电影电视剧在线观看| 中文一区在线| 欧美www视频在线观看| 一区二区三区高清在线观看| 国产啪精品视频| 欧美寡妇偷汉性猛交| 亚洲影院高清在线| 亚洲第一区在线观看| 亚洲专区欧美专区| 亚洲国产成人在线播放| 国产精品久久中文| 欧美jjzz| 性色av香蕉一区二区| 亚洲激情在线观看视频免费| 久久成人人人人精品欧| 夜夜嗨av一区二区三区| 精品动漫3d一区二区三区免费版| 欧美日韩一区不卡| 久久亚洲国产成人| 欧美一区不卡| 一级成人国产| 亚洲高清一区二| 久久全球大尺度高清视频| 在线亚洲欧美| 亚洲卡通欧美制服中文| 国内精品久久久久久久影视麻豆| 欧美色视频一区| 欧美激情一区二区三级高清视频| 欧美中文字幕视频在线观看| 在线亚洲免费视频| 亚洲精品免费看| 亚洲电影第1页| 可以免费看不卡的av网站| 欧美在线观看视频在线| 亚洲欧美日韩国产一区二区| 亚洲精品一区中文| 亚洲国产岛国毛片在线| 国产一区二区三区在线免费观看 | 欧美日韩亚洲综合一区| 香蕉成人久久| 欧美一级二级三级蜜桃| 亚洲一级二级| 亚洲天堂av图片| 一本一本久久a久久精品综合麻豆| 美女被久久久| 免费欧美日韩| 亚洲欧美日韩一区二区| 午夜激情一区| 亚洲欧美中日韩| 午夜激情综合网| 性欧美超级视频| aⅴ色国产欧美| 一区二区三区精密机械公司| 韩国av一区二区| 精品成人一区二区| 伊人精品在线| 亚洲欧洲在线一区| 最近看过的日韩成人| 最近中文字幕日韩精品| 亚洲精品久久久久久下一站| 日韩午夜电影av| 亚洲视频国产视频| 亚洲欧美区自拍先锋| 亚洲欧美日韩在线播放| 久久aⅴ乱码一区二区三区| 久久久久久网站| 欧美激情国产日韩精品一区18| 亚洲大胆在线| 99re视频这里只有精品| 亚洲综合激情| 久久久久在线| 欧美伦理影院| 国产精品劲爆视频| 国产欧美日韩精品丝袜高跟鞋| 影视先锋久久| 夜夜嗨av一区二区三区网站四季av| 99re视频这里只有精品| 亚洲一二三区在线观看| 久久人人97超碰精品888| 欧美激情一区三区| 一本大道av伊人久久综合| 欧美一级久久| 欧美大秀在线观看| 国产欧美精品一区二区三区介绍| 一区二区三区在线免费观看| 99re亚洲国产精品| 久久久久久久综合| 日韩视频在线你懂得| 羞羞漫画18久久大片| 欧美1级日本1级| 国产精品午夜国产小视频| 国模吧视频一区| 亚洲理伦在线| 亚洲一二三区在线| 久久综合伊人77777蜜臀| 欧美xx视频| 新狼窝色av性久久久久久| 欧美大尺度在线观看| 国产乱码精品一区二区三区av| 91久久极品少妇xxxxⅹ软件| 欧美亚洲色图校园春色| 91久久综合| 久热精品视频在线观看| 国产精品日韩欧美一区二区| 99精品视频网| 欧美不卡视频| 欧美一区二区三区在线观看|