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

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>
            亚洲制服少妇| 性感少妇一区| 国产精品一区二区久久| 欧美视频三区在线播放| 国产精品老牛| 狠狠干狠狠久久| 亚洲日本激情| 亚洲欧美久久久| 欧美一区三区三区高中清蜜桃| 欧美与欧洲交xxxx免费观看| 久久久久久久久久久成人| 欧美成人精品一区| 亚洲黄色天堂| 日韩视频在线你懂得| 亚洲精品久久久久久久久久久久 | 久久精品亚洲热| 久久久久久久性| 免费视频久久| 在线亚洲欧美专区二区| 久久久99免费视频| 欧美日韩中文字幕日韩欧美| 国产一区二区三区免费在线观看| 91久久精品国产91久久| 午夜精品视频在线观看| 麻豆久久婷婷| 亚洲欧美日韩国产一区二区| 免费在线观看成人av| 国产精品美女xx| 亚洲精品国产精品国自产在线| 亚洲欧美日韩人成在线播放| 欧美国产日本在线| 亚洲欧美综合网| 欧美久久影院| 尤物yw午夜国产精品视频| 一区二区三区欧美激情| 麻豆成人在线| 亚洲一区在线播放| 欧美日韩在线一区二区三区| 亚洲高清久久网| 久久国产精品72免费观看| 亚洲麻豆视频| 欧美激情按摩| 亚洲激情电影中文字幕| 久久男人资源视频| 亚洲影院污污.| 欧美午夜一区二区| 亚洲九九爱视频| 亚洲电影av在线| 久久亚洲午夜电影| 有码中文亚洲精品| 久久久精品2019中文字幕神马| 国产亚洲成年网址在线观看| 久久久久九九九九| 国产日产欧产精品推荐色| 亚洲精品国产拍免费91在线| 欧美a级一区二区| 久久久久久一区二区三区| 国产在线观看91精品一区| 欧美中日韩免费视频| 亚洲一区二区三区在线| 欧美日韩一区二区三区在线看 | 亚洲欧美日韩一区二区在线| 日韩亚洲欧美中文三级| 欧美日韩国产专区| 一区二区电影免费观看| 亚洲欧洲精品天堂一级| 欧美日韩高清不卡| 亚洲欧美日韩在线高清直播| 亚洲一区二区三区中文字幕在线| 国产精品久久久久久久免费软件 | 一区二区三区精品| 国产精品ⅴa在线观看h| 欧美在线国产| 久久久噜噜噜久久| 亚洲精品三级| 一区二区三区欧美视频| 国产欧美大片| 狼狼综合久久久久综合网| 久久婷婷丁香| 日韩午夜三级在线| 亚洲一区二区四区| 国产一区在线视频| 欧美肥婆在线| 欧美亚一区二区| 欧美专区18| 欧美国产一区二区在线观看| 亚洲影院色在线观看免费| 亚洲一区二区网站| 最近中文字幕日韩精品| 亚洲午夜精品福利| 国产一区二区毛片| 欧美激情一区二区在线| 欧美亚日韩国产aⅴ精品中极品| 久久久久一区二区| 欧美激情一区二区三区在线| 欧美在线观看你懂的| 欧美激情亚洲另类| 久久久www成人免费毛片麻豆| 欧美激情国产精品| 麻豆精品网站| 国产日韩欧美日韩| 亚洲精品国产拍免费91在线| 国产日韩欧美在线播放不卡| 亚洲国产三级| 在线播放日韩专区| 亚洲在线观看视频网站| 亚洲精品免费一区二区三区| 午夜精品久久久久久久99水蜜桃 | 99国产精品久久久| 欧美一区国产二区| 亚洲综合国产| 欧美久久久久| 欧美国产日韩精品| 国产偷久久久精品专区| 99视频热这里只有精品免费| 亚洲国产导航| 久久久久国产精品厨房| 久久爱www久久做| 国产精品免费网站| 一区二区av在线| 亚洲精品视频一区二区三区| 久久国产综合精品| 久久国产欧美精品| 国产精品视频第一区| 妖精成人www高清在线观看| 亚洲欧洲免费视频| 欧美va天堂在线| 欧美激情一级片一区二区| 伊人成综合网伊人222| 欧美一级视频精品观看| 久久激情视频久久| 国内外成人免费视频 | 一本综合精品| 亚洲精品在线电影| 久久野战av| 欧美国产视频一区二区| 亚洲国产美女久久久久| 欧美成年人视频网站欧美| 91久久精品国产91久久性色tv| 91久久国产综合久久蜜月精品| 老司机精品久久| 欧美成人免费大片| 亚洲日韩成人| 欧美日韩视频第一区| 99国产精品久久久久老师| 亚洲婷婷综合色高清在线| 欧美色精品天天在线观看视频 | 亚洲综合成人婷婷小说| 欧美三级乱码| 亚洲欧美日韩一区二区三区在线 | 老牛嫩草一区二区三区日本| 国内视频一区| 免费久久99精品国产| 亚洲人线精品午夜| 亚洲伊人色欲综合网| 国产手机视频一区二区| 美女91精品| 这里只有精品丝袜| 久久一区二区精品| 亚洲日本乱码在线观看| 欧美日韩四区| 欧美综合国产| 亚洲精品国产精品国自产观看浪潮 | 欧美激情中文字幕在线| 亚洲日本免费电影| 欧美三级韩国三级日本三斤| 午夜视频一区二区| 欧美成人高清| 亚洲欧美日韩一区二区| 一区二区亚洲| 欧美日韩中文在线| 久久久久久午夜| 国产精品99久久久久久白浆小说| 久久久国产午夜精品| 一区二区三区高清不卡| 国产亚洲欧洲一区高清在线观看| 免费看亚洲片| 欧美一区二区三区免费大片| 欧美福利视频一区| 欧美在线视频全部完| 99亚洲精品| 亚洲大片精品永久免费| 国产精品久久久久久久久久免费 | 久久久伊人欧美| 在线一区二区三区四区| 黄色小说综合网站| 国产精品美女久久久| 欧美激情一区| 久久综合九色综合久99| 亚洲在线观看免费| 亚洲精品日韩在线| 欧美电影免费观看网站| 久久久一本精品99久久精品66| 亚洲欧美日韩在线高清直播| 99视频在线精品国自产拍免费观看| 怡红院精品视频| 国内精品国语自产拍在线观看| 国产精品久久看| 国产精品成人一区二区艾草| 欧美人与性动交α欧美精品济南到 |