Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

POJ 1113 :WA。 自己检测不出,贴出代码(已注释),望找出原因,不胜感谢!

Posted by Player000 at 2009-06-08 20:25:10 on Problem 1113
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct _point
{
	int x;
	int y;
} point_t;


int Partition(point_t *pPoint, int beginIndex, int tailIndex)
{
	point_t refPoint = pPoint[beginIndex];
	int i = beginIndex - 1;
	int j = tailIndex + 1;

	while (1)
	{
		while (1)
		{
			i++;
			int crossProducts = pPoint[i].x * refPoint.y - refPoint.x * pPoint[i].y;
			if (crossProducts <= 0)
				break;
		}

		while (1)
		{
			j--;
			int crossProducts = pPoint[j].x * refPoint.y - refPoint.x * pPoint[j].y;
			if (crossProducts >= 0)
				break;
		}

		if (i < j)
		{
			point_t pointTemp;
			pointTemp =  pPoint[i];
			pPoint[i] = pPoint[j];
			pPoint[j] = pointTemp;
		}
		else
		{
			return j;
		}
	}
}


void QuickSort(point_t *pPoint, int beginIndex, int tailIndex)
{
	if (beginIndex < tailIndex)
	{
		int middleIndex = Partition(pPoint, beginIndex, tailIndex);
		QuickSort(pPoint, beginIndex, middleIndex);
		QuickSort(pPoint, middleIndex + 1, tailIndex);
	}
}


int main()
{
	// 读入顶点的个数、半径
	int pointCout, radius;
	scanf("%d %d", &pointCout, &radius);

	// 读入 pointCout 个顶点
	point_t pointArray[1000];
	for (int i = 0; i < pointCout; i++)
	{
		scanf("%d %d", &(pointArray[i].x), &(pointArray[i].y));
	}

	// 找到 y 坐标最小最小的点,当有若干个这样的点时,取 x 坐标最小的那一个,称该点位凸包的初始点
	int initIndex = 0;
	for (int i = 1; i < pointCout; i++)
	{
		if (pointArray[i].y < pointArray[initIndex].y)
		{
			initIndex = i;
		}
		else if (pointArray[i].y == pointArray[initIndex].y && pointArray[i].x < pointArray[initIndex].x)
		{
			initIndex = i;
		}
	}

	// 如果“初始点”的索引不是 0 的话,交换索引为0点和初始点
	if (initIndex != 0)
	{
		point_t pointTemp;
		pointTemp = pointArray[0];
		pointArray[0] = pointArray[initIndex];
		pointArray[initIndex] = pointTemp;
	}

	// 将每个点的坐标减去初始点的坐标,即将原点平移到初始点
	for (int i = pointCout -1; i >= 0; i--)
	{
		pointArray[i].x = pointArray[i].x - pointArray[0].x;
		pointArray[i].y = pointArray[i].y - pointArray[0].y;
	}

	// 对除初始点(原点)以外的点,根据对原点的极角从小到大进行快速排序,
	QuickSort(pointArray, 1, pointCout - 1);

	// 采用 Graham 方法构造凸包
	point_t result[1000];		// result 数组存储凸包的顶点,从初始点开始,按逆时针方向依次存储
	result[0] = pointArray[0];
	result[1] = pointArray[1];
	int maxIndex = 1;
	for (int i = 2; i < pointCout; i++)
	{		
		while (1)
		{
			point_t v1, v2;
			v1.x = result[maxIndex].x - result[maxIndex - 1].x;
			v1.y = result[maxIndex].y - result[maxIndex - 1].y;
			v2.x = pointArray[i].x - result[maxIndex - 1].x;
			v2.y = pointArray[i].y - result[maxIndex - 1].y;

			int crossProduct = v2.x * v1.y - v1.x * v2.y;
			if (crossProduct > 0)
			{
				maxIndex--;
			}
			else if (crossProduct == 0)
			{
				if (abs(v2.y) > abs(v1.y) || abs(v2.x) > abs(v1.x))
				{
					result[maxIndex] = pointArray[i];
				}

				break;
			}
			else
			{
				maxIndex++;
				result[maxIndex] = pointArray[i];
				break;
			}
		} // while (1)
	} // for (int i = 2; i < pointCout; i++)

	// 计算凸包的周长
	double c = 0, dist;
	for (int i = 0; i < maxIndex; i++)
	{
		dist = (result[i].x - result[i+1].x)*(result[i].x - result[i+1].x) + (result[i].y - result[i+1].y)*(result[i].y - result[i+1].y);		 
		c = c + sqrt(dist);
	}

	dist = (result[0].x - result[maxIndex].x)*(result[0].x - result[maxIndex].x) + (result[0].y - result[maxIndex].y)*(result[0].y - result[maxIndex].y);
	c = c + sqrt(dist);

	// 凸包的周长加上圆的周长即为最后的结果
	c = c + radius*2*3.1415926535;

	printf("%.0lf", c);

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator