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 |
求助:为什么所有找的测试数据都对了,还是WA?#include <iostream> #include <algorithm> #include <math.h> using namespace std; #define pi 3.14159265 int N,L; struct point { int x,y; }; struct point pnt[1005],res[1005]; bool mult(point sp, point ep, point op) { return (sp.x - op.x) * (ep.y - op.y) >= (ep.x - op.x) * (sp.y - op.y); }; bool operator < (const point &l, const point &r) { return l.y < r.y || (l.y == r.y && l.x < r.x); }; int graham(int n) { int i, len, k = 0, top = 1; sort(pnt, pnt + n); if (n == 0) return 0; res[0] = pnt[0]; if (n == 1) return 1; res[1] = pnt[1]; if (n == 2) return 2; res[2] = pnt[2]; for (i = 2; i < n; i++) { while (top && mult(pnt[i], res[top], res[top-1])) top--; res[++top] = pnt[i]; } len = top; res[++top] = pnt[n - 2]; for (i = n - 3; i >= 0; i--) { while (top!=len && mult(pnt[i], res[top], res[top-1])) top--; res[++top] = pnt[i]; } return top; // 返回凸包中点的个数 } double Distance( point a, point b ) { return sqrt( (double)(a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) ); } int main() { int i,x,y,nr; double dis; while ( scanf( "%d%d",&N,&L ) != EOF ) { for ( i = 0; i < N; ++ i ) { scanf( "%d%d",&pnt[i].x,&pnt[i].y ); } nr = graham(N); //printf("%d\n",nr); dis = 0; for ( i = 1; i < nr; ++ i ) { dis += Distance(res[i-1], res[i]); } dis += Distance(res[0],res[nr-1]); dis += 2 * pi * L; printf("%d\n",(int)(dis+0.5)); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator