P2742 【模板】二维凸包 / [USACO5.1]圈奶牛Fencing the Cows

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

12.00


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

//P2742 【模板】二维凸包 / [USACO5.1]圈奶牛Fencing the Cows
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 10005;
typedef pair<double, double> _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
", Dis);
    }
    return 0;
}