题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1： 

44 84 125 9.37 8

输出样例#1： 

12.00 听说是二维凸包模板题，就找来做了。计算几何写起来好麻烦啊orz 解题过程注释里感觉写的很详细了，就不废话了，直接放代码好了。 二维凸包详细的计算方法在这里。（不要脸的骗访问哈哈哈qaq）

//P2742 【模板】二维凸包 / [USACO5.1]圈奶牛Fencing the Cows#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn = 10005;typedef pair
           
             _pair;_pair point[maxn];_pair In_Bag[maxn];double Get_Dis (_pair point1, _pair point2){    //计算两点间距离    return sqrt(((point1.first- point2.first)* (point1.first- point2.first) )                + ((point1.second- point2.second)* (point1.second- point2.second) ) );}double Get_axb (_pair a_point1, _pair a_point2, _pair b_point1, _pair b_point2){    //计算两条向量的叉积    //向量a= a_point1 --> a_point2= a_point2- a_point1;    //向量b= b_point1 --> b_point2= b_point2- b_point1;    //叉积axb= (a.x* b.y)- (b.x* a.y);    //a.x= a_point2.x- a_point1.x; a.y= a_point2.y- a_point1.y;    return (((a_point2.first- a_point1.first)* (b_point2.second- b_point1.second) )            - ((b_point2.first- b_point1.first)* (a_point2.second- a_point1.second) ) );}double Get_Cos (_pair point1, _pair point2){    //计算向量a(point1-->point2) 和x轴所成角的余弦值;    point2.first-= point1.first;                //把point1看作坐标原点(0, 0);    point2.second-= point1.second;              //则point2的坐标为(P2.x- P1.x, P2.y- P1.y);    point1.first= 0;    point1.second= 0;    _pair point3;                               //在X轴上找一点P3,做直角三角形;    point3.first= point2.first;                 //P3.x= P2.x;    point3.second= 0;                           //P3.y= P1.y= 0;    double Dis_P1_P2= Get_Dis(point1, point2);  //计算直角三角形的斜边长,即P1P2之间的距离;    return point3.first/ Dis_P1_P2;             //邻边/ 斜边;}bool cmpx_0 (_pair a, _pair b){    //小于运算(y,x尽量小);    if (a.second == b.second) return a.first- b.first< 0;    return a.second- b.second< 0;}bool cmpx_1 (_pair a, _pair b){    //小于运算(按与基点P0所成向量的余弦值大小,余弦值越大越优先;cosx在[0,Pi]内从1到-1，减函数；    //排序后,按逆时针方向遍历点集;    _pair tmp = point[0];                       //基点;    double Cos_a = Get_Cos(tmp, a);             //求出a,b的余弦值;    double Cos_b = Get_Cos(tmp, b);    return Cos_a- Cos_b> 0;                     //余弦值越大越优先(越大逆时针遍历越靠前);}int main(){    int n;    double x, y;    while (cin >> n)    {        for (int i = 0; i < n; i ++)        {            cin >> x >> y;            if (i )            {                if (y< point[0].second|| (y== point[0].second&& x< point[0].first) )                {                    double tmp= y;                    y= point[0].second;                    point[0].second= tmp;                    tmp= x;                    x= point[0].first;                    point[0].first= tmp;                }            }            point[i].first= x;            point[i].second= y;        }        sort(point+ 1, point+ n, cmpx_1);        int cnt= -1;                          //cnt -->In_Bag[]中最后一位元素的数组下标;        In_Bag[++ cnt]= point[0];        for (int i = 1; i < n; i ++)          //从point[1]开始;        {            while (cnt&& Get_axb(In_Bag[cnt- 1], In_Bag[cnt], In_Bag[cnt], point[i])< 0 )            {                //当In_Bag中至少有基点和另一点时(cnt>= 1时);                //逆时针扫描时,如果向量{Pn-1, Pn}与{Pn, Pn+1}的叉积为负,则将上一点删除;                //(顺时针扫描判断是否为正)                -- cnt;            }            In_Bag[++ cnt]= point[i];        }        double Dis = 0;        for (int i= 0; i<= cnt; i ++)        {            Dis+= Get_Dis(In_Bag[i], In_Bag[(i+ 1)% (cnt+ 1)]);        }        printf("%.2f\n", Dis);    }    return 0;}