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

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>
            蜜臀av在线播放一区二区三区| 国产亚洲精品bv在线观看| 欧美不卡一区| 夜夜嗨av一区二区三区四区| 欧美一区二区| 日韩视频免费大全中文字幕| 久久久免费av| 一个人看的www久久| 亚洲国产影院| 亚洲日本va午夜在线电影| 欧美在线黄色| 国产精品第一页第二页第三页| 欧美黄网免费在线观看| 欧美日韩八区| 国产精品久久久一区麻豆最新章节| 亚洲综合另类| 亚洲天堂久久| 久久精品国产精品| 久久野战av| 欧美精品啪啪| 国产在线拍揄自揄视频不卡99 | 亚洲精品三级| 亚洲午夜视频在线| 久久久www免费人成黑人精品| 蜜桃久久精品一区二区| 欧美三级资源在线| 永久久久久久| 午夜在线电影亚洲一区| 国产精品高精视频免费| 欧美一级淫片aaaaaaa视频| 老色批av在线精品| 国产精品外国| 亚洲欧洲综合另类| 亚洲欧美综合v| 亚洲国产成人高清精品| 亚洲在线网站| 欧美激情综合在线| 在线观看中文字幕不卡| 亚洲一区二区在线看| 欧美成人综合在线| 香蕉乱码成人久久天堂爱免费| 欧美日韩第一区日日骚| 精品动漫3d一区二区三区| 日韩一区二区免费看| 久久免费视频在线观看| 一区二区三区视频在线观看| 玖玖综合伊人| 国产精品美女久久| 亚洲国产精品激情在线观看| 欧美在线不卡视频| 亚洲一区在线播放| 欧美日韩精品一区| 99re6热只有精品免费观看| 久久综合一区| 日韩亚洲欧美一区| 亚洲午夜精品一区二区| 亚洲区一区二区三区| 欧美成人午夜激情| 一区二区三区高清不卡| 亚洲在线一区| 日韩亚洲欧美成人一区| 欧美高清在线一区| 正在播放日韩| 1769国内精品视频在线播放| 亚洲一区二区不卡免费| 亚洲人体一区| 欧美日韩一区二区三区| 欧美日韩天天操| 亚洲影院在线| 久久一区二区三区av| 亚洲精品日韩在线| 午夜在线精品| 国产揄拍国内精品对白 | 国产一级精品aaaaa看| 欧美一区成人| 欧美亚洲免费| 亚洲国产精品123| 亚洲激情在线观看| 欧美日韩一区自拍| 久久av红桃一区二区小说| 久久九九精品99国产精品| 亚洲二区在线视频| 亚洲精品国产日韩| 国产精品h在线观看| 欧美专区一区二区三区| 久久久91精品国产一区二区三区| 亚洲国产va精品久久久不卡综合| 99精品视频免费| 在线视频日韩| 精品福利电影| 亚洲精品一区二区在线观看| 国产精品久久久久久久久久久久久久| 国产一区视频在线看| 美女脱光内衣内裤视频久久影院| 欧美在线免费| 欧美sm视频| 欧美三级在线| 蜜月aⅴ免费一区二区三区| 欧美国产先锋| 久久大香伊蕉在人线观看热2| 老司机凹凸av亚洲导航| 亚洲午夜一区| 男同欧美伦乱| 久久国产精品99国产精| 欧美激情麻豆| 久久国产一二区| 欧美乱人伦中文字幕在线| 久久国产视频网| 欧美三级电影大全| 欧美大胆人体视频| 国产日产精品一区二区三区四区的观看方式| 老司机aⅴ在线精品导航| 亚洲一级特黄| 亚洲人午夜精品| 老司机aⅴ在线精品导航| 国产精品xxxxx| 玖玖国产精品视频| 国产精品理论片| 亚洲激情欧美激情| 一区二区三区我不卡| 一区二区免费在线播放| 在线观看亚洲一区| 亚洲欧美日韩国产中文| 亚洲免费观看| 久久亚洲精品网站| 久久久噜噜噜久久中文字免| 国产精品白丝jk黑袜喷水| 亚洲国产日韩在线一区模特| 黄网站色欧美视频| 亚洲欧美视频| 亚洲欧美国产77777| 欧美α欧美αv大片| 久久久综合免费视频| 国产精品一区二区久久精品| 日韩视频免费观看高清在线视频| 亚洲日本免费电影| 欧美电影免费观看大全| 亚洲高清视频一区| 亚洲国产另类久久久精品极度| 欧美在线免费视屏| 亚洲区一区二区三区| 一本综合精品| 亚洲一区二区三区777| 欧美日韩综合| 亚洲一区二区三区国产| 亚洲欧美成人一区二区三区| 欧美日韩国产一区二区| 99www免费人成精品| 欧美77777| 在线免费观看视频一区| 麻豆av一区二区三区久久| 欧美3dxxxxhd| 中文av字幕一区| 国产欧美精品久久| 久久精品首页| 亚洲国产精品一区制服丝袜| 一本色道**综合亚洲精品蜜桃冫| 欧美日韩久久| 亚洲四色影视在线观看| 新狼窝色av性久久久久久| 国产日韩在线视频| 久久综合给合| 亚洲精品乱码久久久久久蜜桃91| 亚洲视频在线观看视频| 国产精品主播| 久久蜜桃av一区精品变态类天堂| 欧美国产免费| 亚洲综合精品四区| 伊人婷婷欧美激情| 欧美国产成人精品| 亚洲一级片在线观看| 鲁大师影院一区二区三区| 一区二区高清在线| 久久婷婷国产综合国色天香| 亚洲精品乱码久久久久久| 久久av一区| 一本一道久久综合狠狠老精东影业 | 亚洲永久视频| 免播放器亚洲| 亚洲一区二区视频在线| 国产视频一区三区| 欧美成人黄色小视频| 亚洲欧美电影院| 亚洲国产精品久久久久秋霞不卡| 亚洲在线国产日韩欧美| 亚洲高清色综合| 欧美系列精品| 免费欧美视频| 欧美影院久久久| 欧美一区二视频在线免费观看| 精品福利电影| 国产精品亚洲人在线观看| 欧美wwwwww| 老司机67194精品线观看| 亚洲欧美欧美一区二区三区| 亚洲日韩中文字幕在线播放| 国产日韩欧美综合| 国产精品久久久久久久久| 欧美成人精品一区二区| 欧美在线视频一区二区三区|