多边形整点

发布时间: 2017年12月21日 21:52   时间限制: 1000ms   内存限制: 128M

给定边不自相交的n边形,求其边上整点(坐标为整数的点)的个数。

输入有多组测试数据。每组的第一行上有正整数n,表示多边形有n个顶点。接着在第二行上有2n个整数x[i], y[i],i=0,1,2,...,n-1,整数之间用一个空格隔开,他们分别表示n边形顺次相连的n个顶点坐标Ai( x[i], y[i]) ,i=0,1,2,...,n-1。

对输入中的每组测试数据,先输出“Case #:”,接着输出给定的多边形内部的整点个数,其中#为测试数据的序号(从1起)。

复制
3
0 0 4 4 0 4
3
1 2 1 3 0 0
4
3 4 0 4 0 -14 -3 -2
Case 1:12
Case 2:3
Case 3:30

geometry

2017ACM程序设计(实践)上机一