#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 1001
#define PI 3.14159265
typedef  struct point{
    int x,y;
}point;

point a[N],b[N+1],s[N];//a[]为输入，b[]为排序结果，s[]为栈
int top,n,l;//top为栈顶，n、l为输入

void sort()//排序结果保存在b[]中
{
    int i,j,index=1;
    for(i=2;i<=n;i++){//找出y最大(最高)的点；若有多个，则找出x最小的。
        if(a[i].y>a[index].y || a[i].y==a[index].y&&a[i].x<a[index].x)
            index=i;
    }
    j=1;
    for(i=index;i<=n;i++)
        b[j++]=a[i];
    for(i=1;i<index;i++)
        b[j++]=a[i];
    b[j]=a[index];//首尾相连
}

int cross(point p0,point p1,point p2)//差积(p0,p1)X(p0,p2)
{
	int     x1=p1.x-p0.x,
		y1=p1.y-p0.y,
		x2=p2.x-p0.x,
		y2=p2.y-p0.y;
	return (x1*y2-x2*y1);
}

double length(point p1,point p2)
{
    return sqrt((double)((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}

int main()
{
    int i,t;
    double sum;
    while(scanf("%d%d",&n,&l)==2){
        sum=0;
        for(i=1;i<=n;i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        sort();
        top=-1;
        s[++top]=b[1];
        s[++top]=b[2];
        i=3;
        while(i<=(n+1)){
            if(s[top].x==b[i].x && s[top].y==b[i].y)//去除重点
                i++;
            else if(top==0){//栈中只剩一个，入栈
                s[++top]=b[i];
                i++;
            }
            else if((t=cross(s[top-1],s[top],b[i]))<0){//右手系，入栈
                s[++top]=b[i];
                i++;
            }
            else //左手系或共线，出栈
                top--;
        }
        for(i=0;i<top;i++){
           sum+=length(s[i],s[i+1]);
        }
        sum+=2*PI*l;
        printf("%.0f\n",sum);
    }
    return 0;
}

• Re:发现很搞笑:::莫非测试数据...? (1457) qzy6 2006-12-11 13:28:23