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

            題目:

            計算類似這樣一個圖形的面積、邊上的格點數(shù)、內(nèi)部格點數(shù)

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

               

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


               

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

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

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

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

               

                 Farey序列有一個神奇的性質(zhì):前一項的分母乘以后一項的分子,一定比前一項的分子與后一項分母之積大1。用Pick定理來證明這個結(jié)論異常簡單。把分母不超過n的每一個0和1之間的分?jǐn)?shù)都標(biāo)在平面直角坐標(biāo)系上,例如0/1就對應(yīng)點(1,0),1/5就對應(yīng)點(5,1)。考慮一根從原點出發(fā)的射線由x軸正方向逆時針慢慢轉(zhuǎn)動到y(tǒng)軸正方向,這根射線依次掃過的標(biāo)記點恰好就是一個Farey序列(因為Farey序列相當(dāng)于是給每個標(biāo)記點的斜率排序)。考慮這根射線掃過的兩個相鄰的標(biāo)記點,它們與原點所組成的三角形面積一定為1/2——由于分?jǐn)?shù)都是最簡分?jǐn)?shù),因此它們與原點的連線上沒有格點;又因為這是射線掃過的兩個相鄰的標(biāo)記點,因此三角形內(nèi)部沒有任何格點。另外注意到,由于三角形面積等于叉積的一半,因此兩個點(m,n)和(p,q)與原點組成的三角形面積應(yīng)該為(mq-np)/2。于是,對于Farey序列的兩個相鄰分?jǐn)?shù)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 閱讀(282) 評論(0)  編輯 收藏 引用 所屬分類: geometry&phycise

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

            導(dǎo)航

            統(tǒng)計

            公告

            統(tǒng)計系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            狠狠色噜噜狠狠狠狠狠色综合久久| 欧美一级久久久久久久大片| 日本精品一区二区久久久| 91久久精品91久久性色| 99久久国产宗和精品1上映 | 久久w5ww成w人免费| 中文字幕无码久久精品青草| 久久精品国产清自在天天线| 久久精品夜色噜噜亚洲A∨| 久久精品亚洲欧美日韩久久| 亚洲日韩欧美一区久久久久我| 亚洲国产成人精品91久久久| 国产精品美女久久福利网站| 嫩草伊人久久精品少妇AV| 久久久久成人精品无码中文字幕| 精品久久久久久中文字幕| 99久久国产综合精品五月天喷水| 久久久久国产一级毛片高清板| 久久只这里是精品66| 欧美一区二区三区久久综| 高清免费久久午夜精品| 狠狠精品久久久无码中文字幕 | 久久精品水蜜桃av综合天堂| 久久久国产精品亚洲一区| 久久久久四虎国产精品| 久久影院亚洲一区| 俺来也俺去啦久久综合网| 国产L精品国产亚洲区久久| 久久久久久国产精品美女| 久久精品国产福利国产秒| 亚洲国产精品成人AV无码久久综合影院 | 久久精品中文无码资源站| 国产精品丝袜久久久久久不卡| 一本大道久久东京热无码AV| 国产精品久久网| 99久久精品免费看国产一区二区三区 | 亚洲日本va午夜中文字幕久久 | 99re这里只有精品热久久 | 2021国内久久精品| 色综合久久88色综合天天 | 久久99亚洲网美利坚合众国|