| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
POJ 1113 :WA。 自己检测不出,贴出代码(已注释),望找出原因,不胜感谢!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator