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

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

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            亚洲精品午夜国产VA久久成人 | 久久久亚洲裙底偷窥综合| 无码人妻少妇久久中文字幕蜜桃| 日本福利片国产午夜久久| 狠狠色婷婷久久一区二区| 日批日出水久久亚洲精品tv| 亚洲国产美女精品久久久久∴| 亚洲欧美一区二区三区久久| 久久亚洲欧洲国产综合| 91亚洲国产成人久久精品| 66精品综合久久久久久久| 狠狠色丁香婷综合久久| 日韩欧美亚洲综合久久影院d3| 国产精品久久一区二区三区| 91精品国产综合久久精品| 69久久夜色精品国产69| 色偷偷888欧美精品久久久| 久久精品国产亚洲欧美| 国产精品日韩深夜福利久久| 亚洲乱亚洲乱淫久久| 久久久久亚洲AV成人网人人软件 | 久久大香香蕉国产| 国产精品久久免费| 久久996热精品xxxx| 亚洲一区精品伊人久久伊人| 精品久久久久久无码不卡| 99精品国产综合久久久久五月天| 亚洲精品无码久久千人斩| 精品午夜久久福利大片| 久久夜色精品国产| 成人午夜精品无码区久久| 久久九九兔免费精品6| 日产精品99久久久久久| 国产成人无码精品久久久免费| 亚洲国产精品无码久久久久久曰| 精品国产乱码久久久久久呢| 94久久国产乱子伦精品免费| 久久青青草视频| 99久久精品免费国产大片| 久久精品国产99国产精品导航| 久久不射电影网|