usaco_5_1_1_fc.cpp

usaco自己做的1到5章的代码

/*
PROB: fc
LANG: C++
*/
/*
检验凸包模板……
根据模板改良的Graham-Scan算法，用sort来实现nlgn的复杂度
*/
#include<iostream>
#include<memory>
#include<cmath>
#include<algorithm>
using namespace std;
const double INF = 1E200;
const double EP = 1E-10;
const int MAXV = 10001;
const double PI = 3.14159265;

/* 基本几何结构 */
struct POINT
{
	double x;
	double y;
	POINT(double a=0, double b=0) { x=a; y=b;}		//constructor
};
struct LINESEG
{
	POINT s;
	POINT e;
	LINESEG(POINT a, POINT b) { s=a; e=b;}
    LINESEG() { }
};
struct LINE           // 直线的解析方程 a*x+b*y+c=0  为统一表示，约定 a >= 0
{
   double a;
   double b;
   double c;
   LINE(double d1=1, double d2=-1, double d3=0) {a=d1; b=d2; c=d3;}
};
POINT Points[MAXV];
POINT ch[MAXV];
int n,m,len;
double dis;
void init()
{
    int i,j,k;
    freopen("fc.in","r",stdin);
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%lf%lf",&Points[i].x,&Points[i].y);
}
double dist(POINT p1,POINT p2)                // 返回两点之间欧氏距离
{
	return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );
}
double multiply(POINT sp,POINT ep,POINT op)
{
	return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));
}
bool op(POINT a,POINT b)
{
    if(multiply(a,b,Points[0])>0) return true;
    else if(multiply(a,b,Points[0])==0 && dist(Points[0],a)<dist(Points[0],b)) return true;
    return false;
}

void Graham_scan(POINT PointSet[],POINT ch[],int n,int &len)
{
	int i,j,k=0,top=2;
	POINT tmp;
	// 选取PointSet中y坐标最小的点PointSet[k]，如果这样的点有多个，则取最左边的一个
	for(i=1;i<n;i++)
		if ( PointSet[i].y<PointSet[k].y ||
            (PointSet[i].y==PointSet[k].y) && (PointSet[i].x<PointSet[k].x) )
	    	k=i;
	tmp=PointSet[0];
	PointSet[0]=PointSet[k];
	PointSet[k]=tmp;     // 现在PointSet中y坐标最小的点在PointSet[0]
	/*for (i=1;i<n-1;i++)  // 对顶点按照相对PointSet[0]的极角从小到大进行排序，极角相同的按照距离PointSet[0]从近到远进行排序
		{
			k=i;
			for (j=i+1;j<n;j++)
				if ( multiply(PointSet[j],PointSet[k],PointSet[0])>0 ||  // 极角更小
				      (multiply(PointSet[j],PointSet[k],PointSet[0])==0) && // 极角相等，距离更短
				      	        dist(PointSet[0],PointSet[j])<dist(PointSet[0],PointSet[k]) )
 k=j;
			tmp=PointSet[i];
			PointSet[i]=PointSet[k];
			PointSet[k]=tmp;
		}*/
	sort(PointSet,PointSet+n,op);
	ch[0]=PointSet[0];
	ch[1]=PointSet[1];
	ch[2]=PointSet[2];
	for (i=3;i<n;i++)
		{
			while (multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;
			ch[++top]=PointSet[i];
		}
	len=top+1;
}

int main()
{
    int i,j,k;
    init();
    Graham_scan(Points,ch,n,len);
    for(i=0;i<len-1;i++)
        dis+=dist(ch[i],ch[i+1]);
    dis+=dist(ch[0],ch[len-1]);
    freopen("fc.out","w",stdout);
    printf("%0.2lf\n",dis);
    return 0;

}