| ||||||||||
| 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