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