cogs 896 圈奶牛

裸到不能再裸

描述

农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。

PROGRAM NAME: fc

INPUT FORMAT(file fc.in)

输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的放牧点的数目。接下来 N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1,000,000 <= Xi,Yi <= 1,000,000）。数字用小数表示。

OUTPUT FORMAT(file fc.out)

输出必须包括一个实数，表示必须的围栏的长度。答案保留两位小数。

SAMPLE INPUT (file fc.in)

4
4 8
4 12
5 9.3
7 8

SAMPLE OUTPUT (file fc.out)

12.00

凸包最裸的题

直接套板子

Graham扫描法

1. 将点按x坐标第一关键字，y坐标第二关键字排序
2. 首先将p1,p2压入栈中
3. 判断下一个点和栈中最后一个点组成的向量是否在当前前进方向的左边（求下凸壳），如果是的话就入栈，否则弹栈
4. 这样求出了下凸壳，再倒着做一遍就求出来了正凸壳，合起来就是完整的凸包

通过判断叉积是否==0可以控制是否有三点共线的情况

最终栈中的点就是凸包中的点

需要判断，输入不能有重复的点

还有就是坐标不能只按照x或y坐标排序，否则处理不了所有点都在一条直线上的情况

时间复杂度\( O(nlogn) \)，排序慢

代码

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#define N 50000
using namespace std;

const double eps=1e-7;
int dcmp(double x)
{
	if (fabs(x)<eps) return 0;
	else
		if (x>0)
			return 1;
		else
			return -1;
}

const double pi=acos(-1.0);

struct Vector
{
	double x,y;
	Vector (double a=0,double b=0)
	{
		x=a,y=b;
	}
	bool operator < (const Vector &a) const
	{
		return x<a.x||(x==a.x&&y<a.y);
	}
};
typedef Vector Point;

struct Line
{
	Point p;
	Vector v;
	Line(Point P=Point(0,0),Vector V=Vector(0,0))
	{
		p=P,v=V;
	}
};

Vector operator + (Vector a,Vector b) {return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b) {return Vector(a.x-b.x,a.y-b.y);}
Vector operator * (Vector a,double b) {return Vector(a.x*b  ,a.y*b  );}
Vector operator / (Vector a,double b) {return Vector(a.x/b  ,a.y/b  );}
bool   operator ==(Vector a,Vector b) {return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}

Vector Rotate(Vector a,double rad)
{
	return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}

double Dot(Vector a,Vector b)
{
    return a.x*b.x+a.y*b.y;
}

double Len(Vector a){return sqrt(Dot(a,a));}

double Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}

double Cross(Vector a,Vector b)
{
    return a.x*b.y-a.y*b.x;
}

Vector Normal(Vector a)
{
    return Vector(-a.y/Len(a),a.x/Len(a));
}

Point Line_cross(Line a,Line b)
{
	Vector u=a.p-b.p;
	double t=Cross(b.v,u)/Cross(a.v,b.v);
	return a.p+a.v*t;
}

double Dis_To_Line(Point p,Point a,Point b)
{
	return fabs(Cross(a-b,p-b)/Len(a-b));
}

double Dis_To_Seg(Point p,Point a,Point b)
{
	if (a==b) return Len(p-a);
	Vector v=b-a,w=p-a,u=p-b;
	if (dcmp(Dot(v,w)<0))	return Len(w);
	else if (dcmp(Dot(v,u))>0)	return Len(v);
	else return fabs(Cross(v,w)/Len(v));
}

bool Line_Seg_Cross(Point l1,Point l2,Point a,Point b)
{
	Vector v=l1-l2,w=a-l1,u=b-l2;
	return dcmp(Cross(v,w))!=dcmp(Cross(v,u));
}

bool Seg_Cross(Point a1,Point a2,Point b1,Point b2)
{
	double c1=Cross(a2-a1,b1-b1),c2=Cross(a2-a1,b2-a1),
	       c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
	return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}

Point Line_Pro(Point p,Point a,Point b)
{
	Vector v=b-a;
	return a+v*(Dot(v,p-a)/Dot(v,v));
}

double Area_T(Point a, Point b,Point c)
{
	return Cross(b-a,c-a)*0.5;
}

Point TC(Point a,Point b,Point c)
{
	Point p=(a+b)/2,q=(a+c)/2;
	Vector v=Rotate(b-a,pi/2),w=Rotate(c-a,pi/2);
	if (!dcmp(Cross(v,w)))
	{
        if (dcmp(Len(a-b)+Len(b-c)-Len(a-c))==0)
            return (a+c)/2;
        if (dcmp(Len(a-c)+Len(b-c)-Len(a-b))==0)
            return (a+b)/2;
        if (dcmp(Len(a-b)+Len(a-c)-Len(b-c))==0)
            return (b+c)/2;
    }
    return Line_cross(Line(p,v),Line(q,w));
}

Point TG(Point a,Point b,Point c)
{
    return (a+b+c)/3;
}

double Area_P(Point ploy[],int num)
{
	double area=0;
	for (int i=2;i<num;i++)
		area+=Cross(ploy[i]-ploy[1],ploy[i+1]-ploy[1]);
	return area/2;
}

bool Point_In_Ploy(Point p,Point poly[],int num)
{
	int ans=0,k,d1,d2;
	for (int i=1;i<=num;i++)
	{
		if (!dcmp(Dis_To_Seg(p,poly[i],poly[i%num+1]))) return 0;
		k=dcmp(Cross(poly[i%num+1]-poly[i],p-poly[i]));
		d1=dcmp(poly[i].y-p.y);
		d2=dcmp(poly[i%num+1].y-p.y);
		if (k>0&&d1<=0&&d2>0) ++ans;
		if (k<0&&d1>=0&&d2<0) --ans;
	}
	if (ans) return 1;
	return 0;
}

Point stack[N];int top;
void Graham(Point p[],int num)
{
	memset(stack,0,sizeof stack);top=0;
	sort(p+1,p+num+1);
	for (int i=1;i<=num;i++)
	{
		while (top>1 && dcmp(Cross(stack[top]-stack[top-1],p[i]-stack[top-1]))<=0)
			top--;
		stack[++top]=p[i];
	}
	int k=top;
	for (int i=num-1;i>=1;i--)
	{
		while (top>k && dcmp(Cross(stack[top]-stack[top-1],p[i]-stack[top-1]))<=0)
			top--;
		stack[++top]=p[i];
	}
	if (num>1) top--;
}

main()
{
	freopen("fc.in","r",stdin);
	freopen("fc.out","w",stdout);
	int n;
	scanf("%d",&n);
	double x1,x2,x3,x4,y1,y2,y3,y4;
	Point p[N];
	for (int i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	Graham(p,n);
	double ans=0;
	for (int i=2;i<=top;i++)
		ans+=Len(stack[i]-stack[i-1]);
	ans+=Len(stack[top]-stack[1]);
	printf("%.2lf",ans);
}