• <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>

            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 閱讀(291) 評論(0)  編輯 收藏 引用 所屬分類: geometry&phycise

            <2011年9月>
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            大伊人青草狠狠久久| 亚洲日韩中文无码久久| 99国内精品久久久久久久| 久久国产视屏| 麻豆AV一区二区三区久久 | 久久精品一区二区三区AV| 婷婷五月深深久久精品| 99久久www免费人成精品| 久久无码专区国产精品发布| 国产精品久久久久jk制服| 国产高清国内精品福利99久久| 久久人人爽人人爽人人爽 | …久久精品99久久香蕉国产| 精品人妻伦九区久久AAA片69| 成人久久免费网站| 久久九九久精品国产免费直播| 久久天天躁狠狠躁夜夜avapp| 国产精品久久久久乳精品爆| 亚洲精品无码久久久久久| 久久久久久极精品久久久| 久久久青草久久久青草| 久久久精品2019免费观看| 欧美亚洲国产精品久久| 久久亚洲色一区二区三区| 亚洲国产成人久久综合一| 77777亚洲午夜久久多喷| 亚洲第一极品精品无码久久| 亚洲国产一成久久精品国产成人综合 | 久久国产成人精品麻豆| 伊人久久大香线蕉综合热线| 久久九九免费高清视频 | 国产成人99久久亚洲综合精品| 欧美喷潮久久久XXXXx| 久久精品国产99国产精品亚洲| 欧美精品丝袜久久久中文字幕 | 狠狠色综合久久久久尤物| 国产精品美女久久久久网| 久久久久久国产精品无码超碰| 99久久夜色精品国产网站 | 久久最新精品国产| 久久久久综合网久久|