昨天晚上太卡了，竟然没有全部发完，今天早上早早起来发一下，1113是一个计算几何的题目，求得是凸包问题，就是在二维平面上给定一系列的点，求一个最小的凸包将它们全部覆盖，所谓凸包就是一个多边形，在这个多边形内的任意两点间的连线都在多边形内。地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
#include < stdio.h >

#include < stdlib.h >

#include < math.h >

typedef struct
{
    double x;
    double y;
    int addr;
    int flag;
}type;
type p[1005];

int stack[1005];
int top;

void inits( )
{

    top = -1;
}

void in( int a )
{

    stack[++top] = a;
}

void out()
{

    top --;
}

void f_min( int n )
{

    int i;
    type min;

    min.x = p[0].x;
    min.y = p[0].y;
    min.addr = p[0].addr;
    min.flag = p[0].flag;

    for ( i=1; i<n; i++ )
    {
        if ( min.y > p[i].y )
        {
            min.x = p[i].x;
            min.y = p[i].y;
            min.addr = p[i].addr;
            min.flag = p[i].flag;
        }
        else
        {
            if ( min.y == p[i].y )
            {
                if ( min.x > p[i].x )
                {
                    min.x = p[i].x;
                    min.y = p[i].y;
                    min.addr = p[i].addr;
                    min.flag = p[i].flag;
                }
            }
        }
    }
    p[min.addr].x = p[0].x;
    p[min.addr].y = p[0].y;
    p[min.addr].addr = p[0].addr;
    p[min.addr].flag = p[0].flag;
    p[0].x = min.x;
    p[0].y = min.y;
    p[0].addr = min.addr;
    p[0].flag = min.flag;
}

double mul( type *a, type *b, type *c, type *d )
{

    double x1 = a->x - b->x;
    double y1 = a->y - b->y;
    double x2 = c->x - d->x;
    double y2 = c->y - d->y;

    return x1 * y2 - x2 * y1;
}

double dis( type *a, type *b )
{

    double x = a->x - b->x;
    double y = a->y - b->y;
    return x*x + y*y;
}

int cmp( const void *a, const void *b )
{

    type *c = ( type * )a;
    type *d = ( type * )b;

    int ans;
    if ( mul( c, &p[0], d, &p[0] ) > 0 )
    {
        ans = -1;
    }
    else if ( mul( c, &p[0], d, &p[0] ) < 0 )
    {
        ans = 1;
    }
    else
    {
        if ( dis( c, &p[0] ) > dis( d, &p[0] ) )
        {
            ans = 1;
        }
        else 
        {
            if ( dis( c, &p[0] ) < dis( d, &p[0] ) )
            {
                ans = -1;
            }
        }
    }

    return ans;
}

int aobao( int n )
{

    int i;
    int ans = 1;

    f_min( n );

    qsort( p+1, n-1, sizeof( type ), cmp );

    inits();

    in( 0 );
    p[0].flag = 1;

    for ( i=1; i<n-1; i++ )
    {    
        if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
        {
            break;
        }
    }
    in( i );
    p[i].flag = 1;

    if ( i == n-1 )
    {
        ans = 0;
        return ans;
    }

    for ( ++i; i<n-1; i++ )
    {
        if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
        {
            break;
        }
    }
    in( i );
    p[i].flag = 1;
        
    for ( ++i; i<n; i++ )
    {
        if ( i < n-1 )
        {
            if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
            {
                while ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) >= 0 )
                {
                    p[stack[top]].flag = 0;
                    out();
                }

                in( i );
                p[i].flag = 1;
            }
        }
        else
        {
            while ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) >= 0 )
            {
                p[stack[top]].flag = 0;
                out();
            }

            in( i );
            p[i].flag = 1;
        }
    }

    return ans;
}

int main()
{

    int n;
    double l;
    double ans;
    int temp;
    int i;

    while ( scanf( "%d%lf", &n, &l ) != EOF )
    {
        for ( i=0; i<n; i++ )
        {
            scanf( "%lf%lf", &p[i].x, &p[i].y );
            p[i].addr = i;
            p[i].flag = 0;
        }

        temp = aobao( n );
    
        ans = 0;
        for ( i=1; i<=top; i++ )
        {
            ans += sqrt( dis( &p[stack[i]], &p[stack[i-1]] ) );
        }
        if ( temp )
        {
            ans += sqrt( dis( &p[stack[top]], &p[stack[0]] ) );
        }
        ans += 2 * l * acos(-1);
 
        printf( "%d\n", ( int )( ans+0.5 ) );
    }

        return 0;
}