学步园

题目链接：http://poj.org/problem?id=1113

解题报告参见  http://blog.csdn.net/lyy289065406/article/details/6648622

第一次写凸包的题，发现还有许多细节没有完全掌握。。。

公式：城堡围墙长度最小值 = 城堡顶点坐标构成的散点集的凸包总边长 + 半径为L的圆周长（推导见上述解题报告）

极角序

#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

struct point
{
    double x,y;
};
 
const double EPS=1e-8;
const int MAX=1005;
const double PI=acos(-1.0);
point p[MAX],q[MAX],temp;
int n,m;

int DB (double x)
{
    if (x>EPS)
		return 1;
    if (x<-EPS)
		return -1;
    return 0;
}

double Dis (point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

//判断p在向量ab的哪一侧
//右侧：返回正值
//左侧：返回负值
//在向量ab上返回0
double cross(point a,point b,point p)
{
    return (b.x-a.x)*(p.y-a.y)-(b.y-a.y)*(p.x-a.x);
}

int cmp (point a,point b)
{
    double x=Dis(a,temp),y=Dis(b,temp);
    int flag=DB(cross(temp,a,b));
    if (flag)
		return flag == 1;
    return
		DB(x-y)<=0;
}
 
//求凸包函数
//p:所有的点，n个,p[0]到p[n-1]
//q:求完的凸包中的点，m个,q[0]到q[m-1]
void Graham (point p[],int n,point q[],int &m)
{
    point t;
    int i,k=0,a,b;
    for (i=1;i<n;i++)
    {
        a=DB(p[i].y-p[k].y);
        b=DB(p[i].x-p[k].x);
        if (a==-1 || !a && b==-1)
			k=i;
    }
    if (k!=0)
		t=p[0],p[0]=p[k],p[k]=t;
    temp=p[0];
    sort(p+1,p+n,cmp);
    q[0]=p[0];
    q[1]=p[1];
    p[n]=p[0];
    m=2;
    for (i=2;i<=n;i++)
    {
        while (m>1 && DB(cross(q[m-2],q[m-1],p[i]))<=0)
			m--;
        q[m++]=p[i];
    }
    m--;     //头尾是同一个点
}

int main ()
{
	int L,i;
	double ans=0;
	scanf("%d%d",&n,&L);
	for (i=0;i<n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	Graham (p,n,q,m);
	for (i=0;i<m;i++)
		ans+=Dis(q[i],q[(i+1)%m]);
	ans+=PI*2*L;
	printf("%.0lf\n",ans);
	return 0;
}

水平序

#include <stdio.h>
#include <string.h>
#include <algorithm>  
#include <math.h>  
using namespace std; 

const double PI=acos(-1.0);
struct Point
{  
    double x,y;

	void get()
	{
		scanf("%lf%lf",&x,&y);
    }
}pt[1005],ch[1005];

int n,len;

int DB (double d)
{
	if (fabs(d)<1e-8)
		return 0;
	return d>0?1:-1;
}

double Dis (Point p,Point ch)
{
	return sqrt((p.x-ch.x)*(p.x-ch.x)+(p.y-ch.y)*(p.y-ch.y));
}

double cross (Point p,Point ch,Point x)
{
	return (p.x-x.x)*(ch.y-x.y)-(ch.x-x.x)*(p.y-x.y);
}

int cmp (const void *a,const void *b)
{
	Point aa=*(Point *)a;
	Point bb=*(Point *)b;
	int y=DB(aa.y-bb.y);
	int x=DB(aa.x-bb.x);

	if (y == 0)
		return x==1?1:-1;
	return y;
}

void Graham (Point pt[],Point ch[],int &len,int n)      //只保存凸包顶点
{
	int i,top=1;
	qsort(pt,n,sizeof(pt[0]),cmp);
    ch[0]=pt[0];
    ch[1]=pt[1];
    for (i=2;i<n;i++)
    {
        while (top>0 && DB(cross(ch[top],pt[i],ch[top-1])) <= 0)
            top--;
        ch[++top]=pt[i];
    }
    int temp=top;
    for (i=n-2;i>=0;i--)
    {
        while (top>temp && DB(cross(ch[top],pt[i],ch[top-1])) <= 0)
            top--;
        ch[++top]=pt[i];
    }
    len=top;
}

int main ()
{
    int L,i;  
    double ans=0;
    scanf("%d%d",&n,&L);  
    for (i=0;i<n;i++)  
        pt[i].get();
    Graham (pt,ch,len,n);
    for (i=0;i<len;i++)
        ans+=Dis(ch[i],ch[(i+1)%len]);  
    ans+=PI*2*L;
    printf("%.0lf\n",ans);
    return 0;
}