由于原题是英文的,我的翻译可能有点别扭,所以再多说明一下。
格点:坐标系内系数为整数的点。
格点多边形的定义:坐标系内所有顶点系数为整数的多边形。
格点多边形的“相对格点多边形”:将原格点多边形形上(包括边上和角上)的所有格点按逆时针方向记下,记为A1,A2,A3,A4,A5...An,记其坐标向量为p1,p2,p3,p4,p5...pn.
令qi=(pi+1)-(pi),例q1=p2-p1,q2=p3-p2。令qn=p1-pn。在坐标系内依次连结q1至qn,可得一新多边形,即为原格点多边形的“相对格点多边形”。
现求证:若以格点多边形形内只有一个格点(原点),(形上可有其他格点),则该多边形与其“相对格点多边形”面积和为6。
附注:我现在已可证出相对格点多边形形内也有原点。解此问题可能要用到皮克公式,即A=I+B/2-1.
A:多边形面积
I:多边形形内格点数
B:多边形形上格点数
原多边形为凸多边形
嗯 是凸多边形。。
注意:A1,A2,A3...An 是原多边形上的所有格点,包括边上的格点。
所以你举的正方形上的格点为 A1(1,1), A2(0,1), A3(-1,1), A4(-1,0), A5(-1,-1), A6(0,-1), A7(1,-1), A8(1,0)
正方形面积是4,
q1(-1,0), q2(-1,0), q3(0,-1), q4(0,-1), q5(1,0), q6(1,0), q7(0,1), q8(0,1)
新正方形面积为2
面积和是6
实在不行只能枚举了。。。
先证三角形,再证四边形。。。直到证多于x(这个东西比12小)边形至少要包含2个格点
除此之外我没想到什么方法
GOT IT!
首先你定义的格点n边形的面积为n/2
如果是边上恰有三个格点的三角形的话结论是不证自明的,由等积变换可以知道相对三角形面积是原三角形的3倍。(图:http://hiphotos.baidu.com/qweytr_1/pic/item/f4dc11fab2fb4316ce17c73720a4462308f7d3a2.jpg
发不上来)
{剩下的就可以枚举了,情况不多}
实在不行用公式S=1/2(a1b2-a2b1)((a1,b1),(a2,b2),(0,0)三点逆时针排列,否则公式前加-号)
{各种计算之后知:只需证6=n-(a[i]b[i+2]-a[i+2]b[i]的累加(规定X[n+m]=X[m]))}
现在,对形上的格点数n归纳:
设当n=k(k>=3)时成立,当n=k+1时,可以轻易证出那些对于任意a[n]a[n+2]连线均过原点的情况(这是个平行四边形,面积为2,对这类图形枚举即可,此处从略)
若存在i使a[i]a[i+2]不过原点,则见图http://hiphotos.baidu.com/qweytr_1/pic/item/bbbf48f2d7ca7bcba69e7862be096b63f424a8cd.jpg
从图中显然可以看出:将a[i+1]看作新加入的点
证明6=n-(a[i]b[i+2]-a[i+2]b[i]的累加(规定X[n+m]=X[m]))
只需证多出来的部分(a[i]a[i+1]a[i+2]=1/2(因为这个小三角形被算了两次))
由pick公式,证毕:)
写的不太详细,略去部分自己研究吧,能把这道题想明白,乐趣虽不及解出这道题,但也是聊胜于无的
我已经有答案了,没仔细看你的,不过思路应该是对的。
谢谢。
你举出的三角形上有4个格点,A1(1,1),A2(-1,0),A3(1,-1),以及A4(1,0)
所以有:q1(-2,-1), q2(2,-1), q3(0,1), q4(0,1)
q3和q4重合,故新三角形面积为4
两个面积和是6.
要注意的是,A1,A2,A3...An 是原多边形上的所有格点,包括边上的格点。
这个是我忽略了,我上午有了一个思路,有了个大概,结果被这个例子推翻了,一时疏忽,我回头在整理下,发出来
觉得你是复制一楼的,回复也请参看一楼吧
谢谢