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

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>
            亚洲欧美卡通另类91av| 久久亚洲精选| 亚洲欧美视频一区二区三区| 欧美一级专区| 亚洲第一精品福利| 欧美一区二区三区四区在线观看地址 | 篠田优中文在线播放第一区| 亚洲综合精品四区| 欧美国产日韩一区二区在线观看 | 一区二区三区www| 一本一本大道香蕉久在线精品| 99热在这里有精品免费| 国产精品99久久99久久久二8| 亚洲夜间福利| 久久精品成人| 亚洲第一精品福利| 亚洲欧美日韩另类| 久久婷婷丁香| 国产精品成人播放| 尤妮丝一区二区裸体视频| 在线观看中文字幕不卡| 日韩一级在线观看| 欧美亚洲免费高清在线观看| 欧美1区2区3区| 日韩网站在线观看| 欧美一区二区高清在线观看| 欧美国产日韩在线| 国内成+人亚洲| 亚洲性感激情| 欧美成人午夜视频| 亚洲一区免费视频| 欧美成人影音| 日韩小视频在线观看专区| 亚洲欧美日韩精品久久奇米色影视| 欧美成人精品一区二区三区| 国产精品久久久久久亚洲调教 | 夜夜嗨av一区二区三区网页| 久久精品亚洲乱码伦伦中文| 亚洲区在线播放| 久久久青草青青国产亚洲免观| 欧美日精品一区视频| 精品不卡一区二区三区| 亚洲一区欧美| 日韩一区二区高清| 欧美电影免费观看高清| 在线免费观看成人网| 欧美一区二区三区视频免费播放| 亚洲成色精品| 久久精品国内一区二区三区| 国产裸体写真av一区二区| 日韩一区二区免费高清| 欧美性感一类影片在线播放 | 亚洲激情在线观看视频免费| 久久丁香综合五月国产三级网站| 亚洲精品视频免费| 男女激情久久| 亚洲高清不卡在线| 免费成人激情视频| 久久精品国产免费观看| 国内精品免费午夜毛片| 久久久夜色精品亚洲| 午夜精品免费在线| 国产精品青草久久| 午夜视频在线观看一区二区三区| 一本一本a久久| 国产精品视频xxxx| 久久久999| 美国十次了思思久久精品导航| 亚洲国产精品久久久久秋霞不卡 | 久久精品综合网| 午夜一区不卡| 国产综合久久| 欧美高清不卡在线| 欧美ab在线视频| 一区二区三区精密机械公司| 夜色激情一区二区| 国产精品日韩欧美一区二区| 午夜亚洲福利| 久久久久这里只有精品| 亚洲福利免费| 亚洲黄色性网站| 欧美性片在线观看| 久久精品亚洲热| 欧美成人有码| 亚洲欧美一区二区激情| 久久精品久久99精品久久| 日韩视频在线永久播放| 亚洲一区二区三区欧美| 红桃视频亚洲| 亚洲精品中文字幕女同| 国产精品网站一区| 你懂的视频欧美| 欧美日韩一区三区四区| 久久久999精品免费| 欧美电影免费观看| 久久久久99精品国产片| 欧美精品久久久久久久久久| 午夜精品亚洲| 欧美va亚洲va香蕉在线| 欧美在现视频| 欧美日韩美女在线| 免费成人毛片| 国产欧美日韩视频在线观看| 亚洲黄色在线| 亚洲大胆美女视频| 亚洲午夜久久久| 亚洲国产三级在线| 欧美怡红院视频一区二区三区| 久久精品夜色噜噜亚洲aⅴ| 欧美激情bt| 久久综合久色欧美综合狠狠 | 亚洲精品一品区二品区三品区| 一区二区三区高清不卡| 亚洲东热激情| 性欧美xxxx大乳国产app| 99天天综合性| 你懂的视频一区二区| 久久国产精品久久久| 欧美日韩一区成人| 亚洲国产精品嫩草影院| 国产在线播放一区二区三区| 一区二区三区高清在线 | 国产午夜精品视频| av成人动漫| 夜夜爽99久久国产综合精品女不卡| 久久久久国产精品www| 久久爱www.| 国产精品高潮呻吟| 99精品热视频| 99精品视频一区| 欧美日韩1区| 亚洲美女视频在线免费观看| 亚洲精品视频在线观看免费| 久久久精彩视频| 久久一区二区三区超碰国产精品 | 日韩亚洲综合在线| 久久一区二区三区四区五区| 久久精品一区二区国产| 国产日韩在线亚洲字幕中文| 亚洲欧美在线观看| 欧美专区福利在线| 国产一级久久| 久久久久成人精品| 欧美99在线视频观看| 亚洲国产清纯| 欧美精品在线免费播放| a91a精品视频在线观看| 亚洲欧美清纯在线制服| 国产精品资源| 欧美伊人久久大香线蕉综合69| 久久久久久亚洲精品杨幂换脸| 国产亚洲成年网址在线观看| 久久狠狠婷婷| 亚洲大片一区二区三区| 亚洲精品美女久久久久| 欧美日韩在线精品| 亚洲欧美激情四射在线日| 久久久久网址| 亚洲理伦在线| 欧美私人啪啪vps| 午夜精品区一区二区三| 免费日韩成人| 亚洲五月六月| 国产一区二区三区久久 | 在线视频日本亚洲性| 欧美日韩国产综合视频在线观看中文 | 在线欧美日韩| 欧美区日韩区| 亚洲一区免费| 欧美激情在线免费观看| 亚洲欧美日韩精品综合在线观看| 国产视频一区欧美| 欧美成人中文| 午夜精品久久久久久久蜜桃app| 免费亚洲电影在线| 亚洲欧美成人一区二区在线电影 | 久久精品亚洲一区二区三区浴池| 欧美激情小视频| 香蕉久久夜色精品国产使用方法| 亚洲高清视频一区| 国产精品国产三级国产普通话三级 | 亚洲人在线视频| 国产精品久久波多野结衣| 欧美一区综合| 国产精品99久久久久久宅男| 猛男gaygay欧美视频| 亚洲欧美日韩中文视频| 亚洲日本电影| 在线免费精品视频| 国产日韩欧美一二三区| 欧美精品久久久久久久久久| 久久久欧美精品| 亚洲欧美变态国产另类| 99精品国产在热久久| 亚洲第一主播视频| 久久亚洲图片| 久久国产精品第一页| 亚洲欧美在线另类| 亚洲一级网站| 国产精品99久久久久久有的能看 |