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

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>
            韩国一区二区三区在线观看| 午夜精品久久久久久久久久久| 亚洲人体影院| 国内偷自视频区视频综合| 国产精品一区久久久久| 国产精品第一区| 国产精品久久久久久久久久久久久 | 欧美性猛交视频| 国产精品成人一区| 国产欧美日韩中文字幕在线| 国产视频丨精品|在线观看| 国产专区精品视频| 亚洲国产日韩一区二区| 99国内精品久久久久久久软件| 一本一道久久综合狠狠老精东影业 | 日韩一级成人av| 亚洲伊人网站| 久久久久久色| 欧美日韩国产色视频| 国产精品综合久久久| 激情欧美日韩一区| 一区二区三区欧美激情| 久久精品国产免费| 欧美好骚综合网| 欧美午夜宅男影院| 在线高清一区| 亚洲欧美日韩在线高清直播| 久久夜色精品国产欧美乱极品| 亚洲激情网站| 欧美一级网站| 欧美三级电影网| 在线精品亚洲| 欧美一级免费视频| 亚洲精品小视频| 久久精品视频一| 国产精品视频久久一区| 蜜桃av一区二区在线观看| 欧美性色aⅴ视频一区日韩精品| 久久久久久久综合| 国产亚洲精品久| 亚洲影院色无极综合| 久久手机免费观看| 国产原创一区二区| 米奇777在线欧美播放| 欧美成人福利视频| 亚洲一区二区毛片| 欧美日韩中文字幕日韩欧美| 欧美大片网址| 久久久久久久久久久一区| 亚洲天堂av高清| 欧美成人日韩| 欧美在线免费视屏| 国产精品免费一区二区三区在线观看| 亚洲激情电影中文字幕| 久久精品夜色噜噜亚洲aⅴ| 99精品欧美一区二区三区| 女人香蕉久久**毛片精品| 狠狠色综合网站久久久久久久| 亚洲欧美综合网| 亚洲视频欧美在线| 欧美三级在线播放| 在线视频精品| 亚洲伦理在线| 欧美日本国产精品| 一本久久综合| av不卡免费看| 国产精品久久精品日日| 亚洲在线视频观看| 亚洲一区二区三区午夜| 国产精品美女xx| 欧美亚洲在线视频| 欧美一区二区黄色| 永久免费视频成人| 欧美激情第3页| 欧美精品电影| 亚洲欧洲精品天堂一级| 久久精品日产第一区二区| 国内精品写真在线观看| 牛夜精品久久久久久久99黑人| 免费观看成人网| 中文亚洲视频在线| 亚洲欧美日本国产专区一区| 国产日韩专区在线| 欧美大片免费观看在线观看网站推荐| 欧美大学生性色视频| 在线亚洲欧美| 香蕉久久夜色精品国产使用方法| 国产三区精品| 在线观看欧美日本| 欧美高清在线观看| 欧美视频在线观看免费| 久久久久久久精| 欧美国产精品| 欧美在线999| 欧美mv日韩mv国产网站app| 亚洲一区二区在线| 久久亚洲国产成人| 亚洲一品av免费观看| 欧美一站二站| 一二三区精品| 久久久91精品| 午夜伦欧美伦电影理论片| 噜噜噜在线观看免费视频日韩| 亚洲在线视频一区| 女人香蕉久久**毛片精品| 午夜精品婷婷| 欧美激情一区二区三区高清视频 | 亚洲一级电影| 欧美一区二区性| 国产精品99久久久久久久女警 | 亚洲国产精品电影| 亚洲五月六月| 亚洲精品中文在线| 欧美一区二区三区在线免费观看| 亚洲精品资源美女情侣酒店| 欧美一区=区| 亚洲欧美国产一区二区三区| 女同一区二区| 麻豆精品在线视频| 国产日韩欧美亚洲一区| 亚洲免费观看高清完整版在线观看| 国内精品免费在线观看| 亚洲一区激情| 亚洲一区二区三区精品动漫| 欧美激情亚洲视频| 另类亚洲自拍| 国内精品久久久久久久97牛牛| 亚洲色图在线视频| 亚洲午夜视频| 欧美日韩国产999| 亚洲电影天堂av| 亚洲国产成人av在线 | 亚洲一区免费看| 免费成人av| 久久一二三四| 国产精品丝袜白浆摸在线| 99riav国产精品| 日韩写真视频在线观看| 欧美大片第1页| 欧美成人激情视频| 亚洲国产欧美一区| 麻豆精品视频| 亚洲国产精品一区| 亚洲精品综合| 欧美日韩免费视频| 中文国产一区| 欧美日韩成人在线视频| 日韩亚洲欧美精品| 午夜免费日韩视频| 国产亚洲永久域名| 久久精品成人欧美大片古装| 久久一区二区三区国产精品| 在线播放视频一区| 欧美成人亚洲| 亚洲视频免费观看| 午夜精品久久久久久久久| 亚洲一区二区在线看| 久久久激情视频| 在线观看日韩av电影| 久久女同精品一区二区| 亚洲国产精品电影| 亚洲小说欧美另类婷婷| 国产欧美日韩在线视频| 久久久精品日韩欧美| 亚洲欧洲精品一区二区三区 | 亚洲日韩欧美视频| 亚洲欧美在线aaa| 亚洲欧美资源在线| 久久综合网络一区二区| 亚洲国产婷婷| 欧美一二三区精品| 亚洲韩国日本中文字幕| 欧美视频中文一区二区三区在线观看 | 国产精品一区二区三区成人| 久久精品国产亚洲一区二区三区| 欧美激情一区二区三区成人| 亚洲视频你懂的| 国模套图日韩精品一区二区| 欧美激情一区二区三区在线视频| 亚洲视频一区二区免费在线观看| 久久久综合网站| 一本大道久久a久久精品综合| 国产女主播视频一区二区| 欧美v日韩v国产v| 午夜精品福利一区二区三区av| 亚洲高清不卡在线| 欧美有码视频| 一区二区三区精密机械公司| 在线观看福利一区| 国产伦精品一区二区三区免费 | 国精产品99永久一区一区| 欧美伦理在线观看| 久久在线视频| 欧美影院成人| 亚洲天天影视| 亚洲免费观看视频| 亚洲韩国日本中文字幕| 蜜臀va亚洲va欧美va天堂| 久久精品免费| 欧美一级黄色网|