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

pku 1265 aera pick定理

題目:

計算類似這樣一個圖形的面積、邊上的格點數、內部格點數

解法:
這里用到一個定理,叫pick定理
面積=邊上點數/2-1+內部點數
然后求邊上的點數直接用gcd(dx,dy)就可以了。
網格圖是一個神奇的圖,里面有很多詭異的結論。
pick定理
Pick定理的幾個出人意料的應用 (摘自matrix67)
Pick定理的幾個出人意料的應用 (摘自matrix67)
2009-11-13 11:34

   

     考慮直線x+y=n,其中n是一個素數。這條直線將恰好通過第一象限里的n-1個格點(如上圖,圖中所示的是n=11的情況)。將這n-1個點分別和原點相連,于是得到了n-2個灰色的三角形。仔細數數每個三角形內部的格點數,你會發現一個驚人的事實:每個三角形內部所含的格點數都是一樣多。這是為什么呢?


   

     Pick定理是說,在一個平面直角坐標系內,如果一個多邊形的頂點全都在格點上,那么這個圖形的面積恰好就等于邊界上經過的格點數的一半加上內部所含格點數再減一。例如,上圖多邊形的邊界上有8個格點,內部含有7個格點,那么其面積就等于8/2+7-1=10。我們曾經在這里看到過一個非常神奇非常詭異的證明。這個定理有一些非常巧妙的應用。在上面的問題里,所有三角形都是等底等高的,因此它們的面積都相等。另外,注意到x與y的和是一個素數,這表明x和y是互素的(否則x+y可以提出一個公因數d,與和為素數矛盾),也就是說(x,y)和原點的連線不會經過其它格點。既然所有三角形的面積都相等,邊界上的格點數也相等,由Pick定理,我們就能直接得出每個三角形內部的格點數也相等了。

     另一個有趣的問題則是,一個n*n的正方形最多可以覆蓋多少個格點?把這個正方形中規中矩地放在直角坐標系上,顯然能夠覆蓋(n+1)^2個格點。貌似這已經是最多的了,不過如何證明呢?利用Pick定理,我們能夠很快說明它的最優性。注意到由于任兩個格點間最近也有一個單位的間距,再考慮到正方形的周長為4n,因此該正方形的邊界上最多有4n個格點。把正方形邊界上的格點數記作B,內部所含格點數記為I,于是它所能覆蓋的總格點數等于I+B,由于I+B = I+B/2-1 + B/2+1 ≤ n^2 + 4n/2 + 1 = (n+1)^2,結論立即得證。

     一個東西最出神入化的運用還是見于那些與它八桿子打不著的地方。Farey序列是指把在0到1之間的所有分母不超過n的分數從小到大排列起來所形成的數列,我們把它記作F_n。例如,F_5就是

0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1

   

     Farey序列有一個神奇的性質:前一項的分母乘以后一項的分子,一定比前一項的分子與后一項分母之積大1。用Pick定理來證明這個結論異常簡單。把分母不超過n的每一個0和1之間的分數都標在平面直角坐標系上,例如0/1就對應點(1,0),1/5就對應點(5,1)。考慮一根從原點出發的射線由x軸正方向逆時針慢慢轉動到y軸正方向,這根射線依次掃過的標記點恰好就是一個Farey序列(因為Farey序列相當于是給每個標記點的斜率排序)??紤]這根射線掃過的兩個相鄰的標記點,它們與原點所組成的三角形面積一定為1/2——由于分數都是最簡分數,因此它們與原點的連線上沒有格點;又因為這是射線掃過的兩個相鄰的標記點,因此三角形內部沒有任何格點。另外注意到,由于三角形面積等于叉積的一半,因此兩個點(m,n)和(p,q)與原點組成的三角形面積應該為(mq-np)/2。于是,對于Farey序列的兩個相鄰分數n/m和q/p,我們有(mq-np)/2 = 1/2,即mq-np=1。



代碼:
 1# include <stdio.h>
 2# define cross(x1,y1,x2,y2) ((x1)*(y2)-(x2)*(y1))
 3int p[105][2];
 4int gcd(int n1,int n2)
 5{
 6    if(n1<0) n1*=-1;
 7    if(n2<0) n2*=-1;
 8    while(n2)
 9    {
10       int t=n1%n2;
11       n1=n2;
12       n2=t;
13    }

14    return n1;
15}

16int main()
17{
18    //freopen("ans.txt","w",stdout);
19    int test,t;
20    scanf("%d",&test);
21    for(t=1;t<=test;t++)
22    {
23         int n,i;
24         int aera=0,edge=0;
25         scanf("%d",&n);
26         for(i=1;i<=n;i++)
27         {
28           scanf("%d%d",&p[i][0],&p[i][1]);
29           edge+=gcd(p[i][0],p[i][1]);
30         }

31         p[0][0]=p[0][1]=0;
32         for(i=1;i<n;i++)
33            p[i][0]+=p[i-1][0],p[i][1]+=p[i-1][1];
34         for(i=2;i<n;i++)
35             aera+=cross(p[i-1][0],p[i-1][1],p[i][0],p[i][1]);
36         printf("Scenario #%d:\n%d %d %.1f\n\n",t,(int)((aera+2-edge)*0.5+1e-6),edge,aera*0.5);     
37    }

38   // system("pause");
39   return 0;
40}

41

posted on 2011-01-16 00:07 yzhw 閱讀(309) 評論(0)  編輯 收藏 引用 所屬分類: geometry&phycise

<2011年1月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

導航

統計

公告

統計系統

留言簿(1)

隨筆分類(227)

文章分類(2)

OJ

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产在线精品一区二区夜色| 欧美夜福利tv在线| 一区二区三区日韩欧美| 在线观看久久av| 欧美成人精品在线| 欧美aⅴ99久久黑人专区| 欧美一区2区三区4区公司二百| 国产精品美女在线| 国产精品视频免费| 一区二区在线观看视频在线观看| 久久大逼视频| 欧美日韩国产丝袜另类| 欧美激情a∨在线视频播放| 欧美日韩成人网| 国产麻豆综合| 亚洲人成在线观看| 亚洲欧美国产另类| 欧美国产先锋| 久久亚洲不卡| 亚洲国产日韩在线一区模特| 亚洲大胆视频| 亚洲欧美国产制服动漫| 老鸭窝91久久精品色噜噜导演| 亚洲视频 欧洲视频| 亚洲欧美中文日韩v在线观看| 亚洲国产婷婷香蕉久久久久久99| 久久亚洲国产成人| 亚洲自拍三区| 欧美v日韩v国产v| 亚洲午夜一区二区| 欧美aⅴ99久久黑人专区| 国产美女精品| 亚洲午夜在线| 亚洲黑丝在线| 亚洲精品字幕| 久久久另类综合| 欧美日韩视频在线一区二区观看视频| 久久9热精品视频| 99视频精品在线| 亚洲国产视频一区二区| 免费欧美网站| 亚洲一区视频在线| 亚洲一区二区三区乱码aⅴ蜜桃女| 亚洲精品国产精品国自产观看 | 亚洲理论在线观看| 亚洲欧洲一级| 国产精品五区| 亚洲精选成人| 欧美大胆a视频| 久久gogo国模裸体人体| 国产精品揄拍500视频| 亚洲一区在线观看免费观看电影高清| 日韩一级片网址| 久久国产精品高清| 亚洲女同在线| 91久久久久久久久久久久久| 亚洲欧美另类综合偷拍| 99综合在线| 欧美影院久久久| 在线综合亚洲欧美在线视频| 亚洲无吗在线| 欧美日韩午夜剧场| 国产视频综合在线| 亚洲另类视频| 国产精品高清网站| 中文欧美字幕免费| 一本大道av伊人久久综合| 日韩午夜在线观看视频| 欧美激情视频一区二区三区在线播放| 欧美日韩第一区| 国产精品女主播| 亚洲欧美日韩精品| 欧美高清你懂得| 欧美成黄导航| 亚洲精品国产视频| 欧美一级大片在线免费观看| 一区二区三区视频在线| 国产精品成人一区| 在线播放日韩专区| 欧美激情欧美激情在线五月| 99国产精品久久久| 性色av香蕉一区二区| 国产午夜精品久久久| 久久久欧美精品sm网站| 欧美在线视频一区二区| 久久精品1区| 男女激情视频一区| 99热免费精品在线观看| 亚洲神马久久| 亚洲第一黄色网| 日韩视频永久免费观看| 国产亚洲精品久久久| 欧美激情免费观看| 国产精品分类| 欧美成人视屏| 国产精品自在在线| 亚洲国产一区二区在线| 国产精品一区视频网站| 欧美高清视频在线观看| 国产精品免费视频xxxx| 欧美激情第10页| 国产欧美日韩综合| 亚洲人在线视频| 美女网站在线免费欧美精品| 国产乱人伦精品一区二区 | 欧美美女操人视频| 亚洲欧美卡通另类91av| 久久九九免费视频| 欧美福利精品| 久久久噜噜噜久久中文字免| 欧美色精品在线视频| 麻豆成人在线观看| 国产精品区一区二区三| 亚洲国产欧美久久| 国内精品视频在线观看| 一区二区三区国产盗摄| 亚洲欧洲日韩综合二区| 久久成年人视频| 销魂美女一区二区三区视频在线| 一本色道久久加勒比88综合| 1769国产精品| 久久久久久成人| 一本色道久久加勒比88综合| 亚洲网站视频| 欧美日韩精品在线播放| 欧美成人精品高清在线播放| 国产美女精品免费电影| 中文日韩欧美| 亚洲天堂免费观看| 欧美啪啪一区| 91久久精品视频| 91久久在线视频| 老司机午夜精品视频| 免费成人你懂的| 亚洲成色www8888| 久久中文在线| 美女精品在线| 亚洲片在线资源| 欧美激情一区二区| 一本色道久久综合亚洲精品小说| 99精品欧美一区二区三区综合在线 | 国产精品成人久久久久| 亚洲欧美成人网| 欧美午夜美女看片| 亚洲综合精品自拍| 久久人人超碰| 最近中文字幕日韩精品| 中文av字幕一区| 亚洲午夜久久久久久尤物| 欧美亚洲成人网| 亚洲免费在线观看| 久久久久久久激情视频| 极品尤物av久久免费看| 欧美成人免费小视频| 日韩亚洲精品在线| 欧美一区二区在线播放| 影视先锋久久| 欧美人与禽猛交乱配视频| 中文精品视频| 免费不卡在线观看av| 99精品99| 国产一二精品视频| 欧美激情综合网| 老司机久久99久久精品播放免费| 欧美激情日韩| 99re66热这里只有精品4| 久久精品99国产精品| 亚洲级视频在线观看免费1级| 亚洲一区二区成人| 亚洲精品日韩欧美| 国产精品久久久久久久电影| 亚洲欧美久久久| 亚洲高清不卡| 西西人体一区二区| 欧美日韩一区二区三区在线看| 久久中文在线| 一区二区三区视频观看| 国产在线精品成人一区二区三区| 亚洲系列中文字幕| 欧美mv日韩mv国产网站| 欧美一区日韩一区| 日韩网站免费观看| 韩日欧美一区二区| 国产精品福利网站| 欧美成人午夜影院| 欧美中文字幕| 亚洲一区二区在线免费观看视频| 亚洲乱码国产乱码精品精 | 国精品一区二区| 久久激情综合网| 欧美在线免费| 亚洲日本va在线观看| 国产午夜精品久久| 国产精品久久久一区二区| 亚洲天堂男人| 亚洲国产婷婷香蕉久久久久久99| 亚洲日本电影在线| 国内免费精品永久在线视频| 久久精品中文字幕一区二区三区| 久久国产精彩视频|