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

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)坐標,要求輸出一個邊數(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大牛這里學到東東。。。(*^__^*) 嘻嘻……  回復(fù)  更多評論
  
# re: POJ 2335 浮點數(shù)的gcd
2008-11-24 23:06 | 11
大牛啊。。最近我都在學習你的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>
            亚洲国产精品va在线观看黑人| 国产日韩欧美在线看| 欧美日韩一级黄| 亚洲人体一区| 亚洲精品一区二区三区蜜桃久 | 国产精品v欧美精品∨日韩| 亚洲精品久久久久久久久久久久| 国产伦精品一区二区三区高清版| 欧美丝袜第一区| 一区二区三区免费看| 亚洲激情在线视频| 欧美美女福利视频| 午夜精品99久久免费| 亚洲欧美视频在线观看视频| 狠狠色丁香久久婷婷综合丁香| 黑人极品videos精品欧美裸| 久久综合一区| 久久综合中文色婷婷| 中文成人激情娱乐网| 亚洲欧美日韩国产另类专区| 激情五月综合色婷婷一区二区| 在线观看中文字幕亚洲| 欧美激情精品久久久六区热门| 亚洲精品黄网在线观看| 国产精品亚洲视频| 欧美成人免费大片| 欧美日韩中文字幕在线视频| 欧美一级淫片aaaaaaa视频| 久久色在线播放| 亚洲天堂久久| 久久影院午夜论| 亚洲永久免费| 美女啪啪无遮挡免费久久网站| 久久青草欧美一区二区三区| 中国成人亚色综合网站| 欧美亚洲免费在线| 亚洲精品久久久久久久久久久久久| 亚洲一区二区精品| 欧美在线日韩| 99精品欧美一区二区三区| 午夜日本精品| 亚洲黄色性网站| 欧美一区二区三区免费大片| 夜夜嗨av一区二区三区网站四季av | 久久男女视频| 亚洲免费在线| 久久综合久久88| 欧美中文字幕在线| 欧美日韩网址| 久久综合狠狠综合久久综青草| 一本色道久久综合| 亚洲国产激情| 久久岛国电影| 欧美在线免费观看| 欧美日韩一区二区国产| 亚洲第一二三四五区| 国内精品久久久久影院 日本资源 国内精品久久久久伊人av | 亚洲一区999| 亚洲欧洲久久| 久热精品视频在线观看一区| 欧美呦呦网站| 欧美精品一线| 亚洲第一综合天堂另类专| 激情久久久久| 久久九九精品99国产精品| 性刺激综合网| 国产精品一区免费在线观看| 一区二区三区三区在线| 一区二区三区回区在观看免费视频| 久久久久综合一区二区三区| 国产欧美日韩免费| 亚洲欧美激情一区| 亚洲欧美日本伦理| 国产精品美女一区二区| 亚洲午夜久久久久久尤物| 亚洲欧美国产va在线影院| 国产精品毛片a∨一区二区三区|国| 午夜精品美女久久久久av福利| 亚洲激情婷婷| 亚洲日本成人| 欧美成人亚洲成人| 日韩视频免费| 亚洲午夜久久久久久久久电影院| 国产精品日韩一区| 亚洲一区二区三区四区五区午夜| 国产欧美一区二区精品秋霞影院| 久久亚洲精品伦理| 亚洲成人在线| 欧美成人精品激情在线观看| 亚洲高清自拍| 亚洲欧美成人一区二区在线电影| 欧美一区二区免费| 久久av红桃一区二区小说| 国产欧美在线观看一区| 久久久久久久999精品视频| 欧美激情视频在线免费观看 欧美视频免费一 | 午夜精品久久久久久99热| 国产区亚洲区欧美区| 久久蜜桃香蕉精品一区二区三区| 亚洲靠逼com| 欧美午夜免费| 久久天天狠狠| 亚洲精品小视频| 亚洲午夜精品国产| 亚洲电影视频在线| 欧美日韩一区二区三区在线视频| 免费日韩av| 亚洲视频在线播放| 激情小说另类小说亚洲欧美| 欧美精品一二三| 欧美在线综合视频| 亚洲美女毛片| 美玉足脚交一区二区三区图片| 欧美日韩hd| 欧美在线视频a| 一本大道av伊人久久综合| 久久精品日产第一区二区| 亚洲人永久免费| 国产自产精品| 国产精品久久久久久久app| 麻豆精品一区二区av白丝在线| 久久不见久久见免费视频1| 韩国精品在线观看| 欧美成人免费小视频| 久久国产精品久久久久久电车| 亚洲清纯自拍| 黄色亚洲在线| 国产伦精品一区二区三区| 欧美日本久久| 欧美成ee人免费视频| 欧美自拍丝袜亚洲| 亚洲在线播放| 在线综合亚洲欧美在线视频| 亚洲精品久久久久久久久久久久久| 国产精品国产一区二区| 欧美一区二区三区视频在线观看| 久久在线精品| 久久久久久网| 久久综合99re88久久爱| 久久日韩精品| 久久免费99精品久久久久久| 久久国产精品黑丝| 久久高清福利视频| 久久久999精品| 久久精品最新地址| 久久嫩草精品久久久久| 久久久伊人欧美| 免费短视频成人日韩| 免费成人黄色| 亚洲国内自拍| 最近中文字幕mv在线一区二区三区四区| 亚洲精品一二三| 亚洲另类一区二区| 一区二区三区欧美在线| 日韩视频一区二区三区| 在线视频欧美日韩| 亚洲免费网站| 久久久精彩视频| 免费观看久久久4p| 久久国产精品第一页| 亚洲欧美一区二区三区在线| 亚洲人久久久| 亚洲淫性视频| 一区二区三区日韩欧美| 91久久精品国产| 在线亚洲精品| 一区二区国产精品| 日韩一级精品视频在线观看| 校园激情久久| 麻豆精品在线观看| 久久一区免费| 久久亚洲综合网| 亚洲开发第一视频在线播放| 欧美国产日本韩| 免费亚洲网站| 美女主播精品视频一二三四| 亚洲精品中文字幕在线| 亚洲欧美日韩电影| 午夜精品一区二区三区四区| 亚洲精品免费一二三区| 亚洲精品中文在线| 久久经典综合| 久久亚洲捆绑美女| 开元免费观看欧美电视剧网站| 99精品国产在热久久婷婷| 亚洲欧洲一区二区在线播放| 亚洲福利视频免费观看| 最新国产乱人伦偷精品免费网站 | 在线成人av| 亚洲第一毛片| 欧美一区二区三区四区在线观看地址 | 久久se精品一区精品二区| 亚洲精品影院在线观看| 亚洲最新中文字幕| 蜜臀久久久99精品久久久久久 | 久久久噜噜噜久久久| 亚洲欧美日韩精品一区二区| 久久久久久成人| 欧美精品v日韩精品v韩国精品v | 久久久亚洲午夜电影|