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到郁闷,以前melkman做的现在graham竟然过不了,求解!!!#include <math.h> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const double Pi = acos(-1.0); const int MAXN = 10010; struct Pt{ int x, y; }p[MAXN]; int top; int s[MAXN]; int Xmul(int x1, int y1, int x2, int y2) { return x1 * y2 - x2 * y1; } int cross(Pt a, Pt b, Pt c) { return Xmul((b.x - a.x), (b.y - a.y), (c.x - a.x), (c.y - a.y)); } int cmp(Pt a, Pt b) { if(a.y == b.y) return a.x < b.x; return a.y < b.y; } void graham(int n) { int i; sort(p + 1, p + n + 1, cmp); s[1] = 1; s[2] = 2; top = 2; for(i = 3; i <= n; i ++) { while(top > 1 && cross(p[s[top - 1]],p[s[top]],p[i]) <= 0) top --; s[++ top] = i; } int len = top; s[++top] = n - 1; for(i = n - 2; i >= 1; i --) { while(top > len && cross(p[s[top - 1]],p[s[top]],p[i]) <= 0) top --; s[++top] = i; } } double dist(Pt a, Pt b) { return sqrt(0.0 + (a.x - b.x) * (a.x - b .x) + (a.y - b.y) * (a.y - b.y)); } double solve(int n) { double sum = 0; graham(n); for(int i = 1; i < top; i ++) sum += dist(p[s[i]],p[s[i + 1]]); return sum; } int main() { int n,l; int i,j; while(scanf("%d%d",&n,&l) != EOF) { memset(p,0,sizeof(p)); memset(s,0,sizeof(s)); for(i = 1; i <= n; i ++) scanf("%d%d",&p[i].x, & p[i].y); double sum = solve(n); sum += 2 * Pi * l; printf("%.0lf\n",sum); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator