首页 > ACM题库 > HDU-杭电 > HDU 3775-Chain Code-计算几何-[解题报告]HOJ
2015
04-10

HDU 3775-Chain Code-计算几何-[解题报告]HOJ

Chain Code

问题描述 :

In a black and white (bi-level) image, collections of connected black pixels can be defined as foreground or objects, while white can be thought of as background. Each set of connected black pixels can be completely described by listing the positions of the pixels on its boundary in counterclockwise order, starting at some arbitrary point on the boundary. This list of pixels can, in turn, be represented simply as the direction to the next one in the list. This list of directions is called the chain code of the object, and describes the shape of the object precisely while being position independent.
There are 8 possible directions from one pixel to an adjacent pixel, and while assigning these numbers is arbitrary, figure 1 shows the standard convention. The direction 0 means “to the right of”, 2 “means immediately above”, and 1 is at 45 degrees, bisecting 0 and 2, and so on.
figure1:
Ropes
Two black pixels are considered to be adjacent if the square of the distance between them is less than or equal to 2. This is based on a standard graphics coordinate system having a pixel at each integer coordinate. Two pixels are connected if a contiguous path of adjacent pixels can be traced between them. A connected region is a set of black pixels in which all members are connected to each other. A boundary pixel of a connected region (from now on just a region) is a pixel within the region that has at least one neighbor (in the four compass directions) that is not black. For this problem, you may assume that there are no “holes” in the region, so that there is only one boundary of the region.The chain code of a region can start at any pixel on the boundary. It proceeds by finding the next adjacent pixel on the boundary in a counter-clockwise direction, saving the direction (0-7) in an output buffer, and then continuing the process from the new pixel. When we arrive at the starting pixel again, the chain code is complete. The output buffer contains a set of direction values which comprise the chain code itself, and from which the original set of pixels can be recreated starting at any pixel position in an image.

As an example, a chain code for the region in figure 2 is 446567001232. The chain code describes the shape of the region unambiguously, although its position is completely unknown. Shape related measures such as perimeter and area (number of pixels in the region) can be determined directly from the chain code description alone. You are to write a program that calculates the area of a connected region given only the chain code.
figure 2
Ropes

输入:

The input will be a collection of chain code strings, one per line. Each chain code contains at most 1000000 characters. You may assume that each chain code describes a valid region, and does not describe a boundary that intersects itself.

输出:

The input will be a collection of chain code strings, one per line. Each chain code contains at most 1000000 characters. You may assume that each chain code describes a valid region, and does not describe a boundary that intersects itself.

样例输入:

446567001232
6024

样例输出:

19
4

 

Pick定理,昨天的比赛居然也需要用到,还好以前学了点计算几何,不然昨天就雪上加霜了……
orz
……

进入正题,Pick
定理是这样的,

S=a+ b/2 - 1
,其中
S是图形面积,
a
是图形内部格点数,
b
是边经过的格点数,适用范围是:顶点坐标均是整点,或者说顶点在格点上的简单多边形。

面积怎么求?三角形的叉乘。

Chain Code

这题很让人郁闷的是,图中的顶点并不是用
pick定理求出的顶点,而还要再加上外面那一圈,也就是还要加上
b

Chain Code

图中橙色的图形表示的是用pick
定理求出的面积,所以还要再加上外面这一圈才是答案。

代码如下:

#include <stdio.h>
#include <string.h>
char str[1000005];
int drow[8]={0,-1,-1,-1,0,1,1,1};
int dcol[8]={1,1,0,-1,-1,-1,0,1};
int main()
{
	__int64 r1,c1,val,r,c,i,j,n;
	__int64 s,ans;
	while(scanf("%s",str)!=EOF)
	{
		n=strlen(str);
		r=c=s=0;
		for (i=0;i<n;i++)
		{
			val=str[i]-'0';
			r1=r+drow[val];
			c1=c+dcol[val];
			s=s+r*c1-c*r1;
			r=r1;
			c=c1;
		}
		if (s<0) s=-s;
		printf("%I64d/n",(n+s)/2+1);
	}
	return 0;
}

参考:http://blog.csdn.net/magicnumber/article/details/6192242


  1. 说实话很不喜欢月见,根本不考虑后果,却被这么多人喜欢,是的她在乎闵星岩,但闵星岩和梵洛伽是一个身体,说实话,这个身体的主导本就属于…强的那个。这样的女主太多,倔强的懦弱。

  2. 说实话很不喜欢月见,根本不考虑后果,却被这么多人喜欢,是的她在乎闵星岩,但闵星岩和梵洛伽是一个身体,说实话,这个身体的主导本就属于…强的那个。这样的女主太多,倔强的懦弱。

  3. 说实话很不喜欢月见,根本不考虑后果,却被这么多人喜欢,是的她在乎闵星岩,但闵星岩和梵洛伽是一个身体,说实话,这个身体的主导本就属于…强的那个。这样的女主太多,倔强的懦弱。

  4. 说实话很不喜欢月见,根本不考虑后果,却被这么多人喜欢,是的她在乎闵星岩,但闵星岩和梵洛伽是一个身体,说实话,这个身体的主导本就属于…强的那个。这样的女主太多,倔强的懦弱。

  5. 说实话很不喜欢月见,根本不考虑后果,却被这么多人喜欢,是的她在乎闵星岩,但闵星岩和梵洛伽是一个身体,说实话,这个身体的主导本就属于…强的那个。这样的女主太多,倔强的懦弱。

  6. 说实话很不喜欢月见,根本不考虑后果,却被这么多人喜欢,是的她在乎闵星岩,但闵星岩和梵洛伽是一个身体,说实话,这个身体的主导本就属于…强的那个。这样的女主太多,倔强的懦弱。