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 |
吐槽 输出%.0lf WA, %.0f AC 不管你信不信,反正我信了!WA代码(把最后输出改成%.0f就AC了): #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int Max = 1100; struct Point { int x; int y; }; int num; Point p[Max]; ///原始点集 Point ch[Max]; ///凸包点集 ///p0p1叉乘p0p2 int xmult(const Point& p0, const Point& p1, const Point& p2) { return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y); } double dis(const Point& a, const Point& b) { return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } ///逆时针顺序把极角排序 bool cmp(const Point& a, const Point& b) { int ret = xmult(p[0],a,b); if(ret>0) return true; if(ret==0&&dis(p[0],a)<dis(p[0],b)) return true; return false; } /** p: 原始点序列 n: 原始点的个数 ch: 栈,用来保存凸包上的点 top: 凸包上点的个数 */ void Graham(Point* p, int n, Point* ch, int& top) { int i,k=0; for(i=1; i < n; i++) { if(p[k].y>p[i].y || ((p[k].y==p[i].y)&&p[k].x>p[i].x)) k = i; } swap(p[k],p[0]); sort(p+1,p+n,cmp); top = 0; ch[top++] = p[0]; ch[top++] = p[1]; ch[top++] = p[2]; for(i = 3; i < n; ch[top++]=p[i++]) while(top>=2 && xmult(ch[top-2],ch[top-1],p[i])<0) ///是否向左 top--; } int main() { int i; int n,l; while(scanf("%d %d",&n,&l)!=EOF) { for(i = 0; i < n; i++) scanf("%d %d",&p[i].x,&p[i].y); Graham(p,n,ch,num); double result = acos(-1.0)*l*2; for(i = 0; i < num-1; i++) result += dis(ch[i],ch[i+1]); result += dis(ch[0],ch[num-1]); printf("%.0f\n",result); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator