#include<stdio.h>
#include<math.h>

int main()
{
	freopen("in.txt","r",stdin);
	double result = 0.0;
	int stack[1001] = {0};
	int ptr = 0;
	int point[1001][2];
	bool In_Circle[1001] = {false};
	int R,n,nextp = 0,now;
	int maxy = 100000,my = 0;
	scanf("%d %d",&n,&R);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d %d",&point[i][0],&point[i][1]);
		if(point[i][1] < maxy)
		{
			my = i;
			maxy = point[i][1];
		}
	}
	double rad[1001] = {0.0};
	int prev[2] = {1,0};
	int nowv[2];
	now = my;//start from my
	stack[0] = my;
	do
	{
		double maxr = -2.0;
		int maxrp = now;
		for(int i = 1;i <= n;i ++)
		{
			if(!In_Circle[i] && i != now)
			{
				nowv[0] = point[i][0] - point[now][0];
				nowv[1] = point[i][1] - point[now][1];
				double dy = (double)((nowv[0]) * (prev[0]) + (nowv[1] * prev[1]));
				double len = (double)(nowv[0] * nowv[0] + nowv[1] * nowv[1]) * (prev[0] * prev[0] + prev[1] * prev[1]);
				rad[i] = (dy / sqrt(len));
				if(maxr < rad[i])
				{
					maxr = rad[i];
					maxrp = i;
				}
			}
		}
		stack[++ptr] = maxrp;
		In_Circle[maxrp] = true;
		prev[0] = point[maxrp][0] - point[now][0];
		prev[1] = point[maxrp][1] - point[now][1];
		now = maxrp;
	}while(now != my);

	result += R * acos(prev[0] * 1.0 / sqrt((double)(prev[0] * prev[0] + prev[1] * prev[1])));

	while(ptr)
	{
		result += acos(rad[stack[ptr]]) * R;
		result += sqrt((double)((point[stack[ptr]][0] - point[stack[ptr - 1]][0]) * (point[stack[ptr]][0] - point[stack[ptr - 1]][0]) + 
							(point[stack[ptr]][1] - point[stack[ptr - 1]][1]) * (point[stack[ptr]][1] - point[stack[ptr - 1]][1])));
		ptr --;
	}
	printf("%.0lf",result);
	return 0;
}

• Re:历时3个小时……终于T T 用ttbobo大牛的数据过的，跪谢~~~~~~~~ (1830) Web_Board 2009-10-06 01:01:45