//下面是学长的模板;;
//题目就不讲了,赤裸裸的凸包。。//注意:须先将n赋值,点数需大于二,求凸包的点的下标放在sta[]中,而不是凸包的点放在point[]中#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>#define pi acos(-1.0)using namespace std;typedef double pointper;//点坐标的类型
#define POINTNUM 50005//最多点的个数
#define PREX 1e-11 //当点坐标为实数型的时候用struct node{ pointper x,y;}Point[10001];class Polygon{ public: int sta[POINTNUM];//在凸包上点的坐标 node point[POINTNUM]; bool flag[POINTNUM]; int top,n,stab;//n为读入的点的个数,top-1为凸包上点的个数,(0~~top-2)是凸包上点的坐标,top-1和0存的都是第一个点; pointper x1,y1,x2,y2; polygon() { top=n=0; } static bool cmp(const node &A,const node &B) { return A.x<B.x||A.x==B.x&&A.y<B.y;//先根据X排序,然后根据Y排序 } bool X(int x1,int y1,int x2,int y2,bool f)//f为true表示求的包括边上的点 { if(f) return x1*y2-x2*y1>=0; return x1*y2-x2*y1>0; } bool X(double x1,double y1,double x2,double y2,bool f)//f为true表示求的包括边上的点 { if(f) return x1*y2-x2*y1>=0.0||fabs(x1*y2-x2*y1)<PREX; return x1*y2-x2*y1>0.0; } void pointselect(bool f);//求凸包上的点,f为true表示求的包括边上的点; void getpoint(int i,bool f); void XY(int i);//辅助X()求叉乘 double length();//求凸包的周长 double area();//求凸包的面积; bool IsInPoly(int x,int y,bool f); bool IsInPoly(double x,double y,bool f);};Polygon Tubao;
void Polygon::XY(int i)
{ x1=point[i].x-point[sta[top-2]].x; y1=point[i].y-point[sta[top-2]].y; x2=point[sta[top-1]].x-point[sta[top-2]].x; y2=point[sta[top-1]].y-point[sta[top-2]].y;}void Polygon::getpoint(int i,bool f)
{ XY(i); if(top==stab||X(x1,y1,x2,y2,f)) { sta[top++]=i; flag[i]=false; } else { top--; flag[sta[top]]=true; XY(i); while(top>stab&&!X(x1,y1,x2,y2,f)) { top--; flag[sta[top]]=true; XY(i); } sta[top++]=i; flag[i]=false; }}void Polygon::pointselect(bool f){ int i; memset(flag,true,n+1); sort(point,point+n,cmp); sta[0]=0; sta[1]=1; top=2; flag[1]=false; stab=1; for(i=2;i<n;i++) getpoint(i,f); stab=top; for(i=n-2;i>=0;i--) if(flag[i]) getpoint(i,f);}double Polygon::length()
{ double s=0.0; int i; for(i=1;i<top;i++) s+=sqrt(1.0*(point[sta[i]].x-point[sta[i-1]].x)*(point[sta[i]].x-point[sta[i-1]].x)+(point[sta[i]].y-point[sta[i-1]].y)*(point[sta[i]].y-point[sta[i-1]].y)); return s;}double Polygon::area(){ double s=0.0; int i; for(i=1;i<top;i++) s+=point[sta[i-1]].x*point[sta[i]].y-point[sta[i]].x*point[sta[i-1]].y; return fabs(s/2);}bool Polygon::IsInPoly(int x,int y,bool f)//int型
{ int i; for(i=1;i<top;i++) if(!X(x-point[sta[i-1]].x,y-point[sta[i-1]].y,(double)point[sta[i]].x-point[sta[i-1]].x,(double)point[sta[i]].y-point[sta[i-1]].y,f)) return false; return true;}bool Polygon::IsInPoly(double x,double y,bool f)//double型
{ int i; for(i=1;i<top;i++) if(!X(x-point[sta[i-1]].x,y-point[sta[i-1]].y,point[sta[i]].x-point[sta[i-1]].x,point[sta[i]].y-point[sta[i-1]].y,f)) return false; return true;}int main()//HDU 1392 求周长
{ while(scanf("%d",&Tubao.n)!=EOF&&Tubao.n) {for(int i=0;i<Tubao.n;i++)
{ scanf("%lf %lf",&Tubao.point[i].x,&Tubao.point[i].y); } if(Tubao.n==1) { printf("0.0\n"); continue; } if(Tubao.n==2) { printf("%.2lf\n",sqrt((Tubao.point[1].x-Tubao.point[0].x)+(Tubao.point[1].y-Tubao.point[0].y))); continue; } Tubao.pointselect(1); printf("%.2lf\n",Tubao.length()); printf("%.2lf\n",Tubao.area()); } return 0;}