题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1392

参考这位童鞋写滴~：
https://blog.csdn.net/xbb224007/article/details/81150946

Graham

①为什么要排个序喃？

因为排序之后阔以减少复杂度，因为我们本来是想转个圈那种来求嘛，如果下一个点就是大概按照逆时针转圈这样来，那就不用到处找下一个最好的点了三，因为就在附近嘛

②为什么要先找最下面最左边的点？

其实你要找最右边最上面的点也没关系，因为反正都是转一圈嘛，只是我们这个最初的这个点一定要是在最后求的凸包上面，也就是要最最最外面一层的点才行
给一个数据：

input：
5
4 7
5 5
5 2
1 8
7 7
output：
18.68

第一个点在里面，不是最外层的点，so~

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL maxn=1e5+5;
const double eps=1e-6;
int N;
struct Point
{
    double x,y;
    Point() {}
    Point(double x,double y):x(x),y(y) {}
};
Point P[maxn];                      //装所有点
Point Convex[maxn];                 //装选出来的凸包点
typedef Point Vector;
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 len)
{
    return Vector(A.x*len,A.y*len);
}
Vector operator/(Vector A,double len)
{
    return Vector(A.x/len,A.y/len);
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double Length(Vector A)
{
    return sqrt(Dot(A,A));
}
bool cmp(Point p1,Point p2)
{
    return Cross(p1-P[1],p2-P[1])>0;        //就是要弄成满足逆时针这样一个一个转着走，用叉积来弄 
}

int Graham(int n)
{
    int pos=1;                  //要赋值为第一个。。。。万一没有进入if里面，那就不晓得是个啥了。。。。WA了好多次。。。 
    Point tp=P[1];
    for(int i=2;i<=N;i++)       //只要找到一个最边边上的点就行了 
    {
        if(P[i].y<tp.y)
        {
            tp=P[i];
            pos=i;
        }
    }
    swap(P[1],P[pos]);
    sort(P+2,P+1+n,cmp);
    Convex[1]=P[1];
    Convex[2]=P[2];
    int top=2;
    for(int i=3;i<=n;i++)
    {
        while(top>=2&&Cross(Convex[top]-Convex[top-1],P[i]-Convex[top-1])<0)top--;//注意这里有些是凸包Convex里的点，不要写成P了
        Convex[++top]=P[i];
    }
    return top;
}
int main()
{
    cout.setf(ios::fixed);
    while(cin>>N&&N)
    {
        for(int i=1; i<=N; i++)cin>>P[i].x>>P[i].y;
        int count=Graham(N);
        double ans=0;
        for(int i=1;i<count;i++)
        {
            ans+=Length(Convex[i]-Convex[i+1]);
        }
        if(count!=2)ans+=Length(Convex[1]-Convex[count]);
        cout<<setprecision(2)<<ans<<endl;
    }
}

Andrew

我的这个代码要是两个点的话，凸包是三个点。。。。。。不知道怎么办了。。。。
但是还是能够算一圈的值是多少

而杭电这道题太坑啦~两个点就不算一圈的，特判一哈就能过

然后就是排序，说的好像是

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL maxn=1e5+5;
const double eps=1e-6;
int N;
struct Point
{
    double x,y;
    Point() {}
    Point(double x,double y):x(x),y(y) {}
};
Point P[maxn];                      //装所有点
Point Convex[maxn];                 //装选出来的凸包点
typedef Point Vector;
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 len)
{
    return Vector(A.x*len,A.y*len);
}
Vector operator/(Vector A,double len)
{
    return Vector(A.x/len,A.y/len);
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double Length(Vector A)
{
    return sqrt(Dot(A,A));
}
bool cmp(Point p1,Point p2)
{
    return p1.x<p2.x;       //也不知道为什么，不判断x相等也能过 
}
int Andrew(int n)
{
    sort(P+1,P+1+N,cmp);
    int top=0;
    for(int i=1;i<=N;i++)
    {
        while(top>=2&&Cross(Convex[top]-Convex[top-1],P[i]-Convex[top-1])<=0)top--;
        Convex[++top]=P[i];
    }
    int k=top;
    for(int i=N-1;i>=1;i--)
    {
        while(top>k&&Cross(Convex[top]-Convex[top-1],P[i]-Convex[top-1])<=0)top--;
        Convex[++top]=P[i];
    }
    return top;
}
int main()
{
    cout.setf(ios::fixed);
    while(cin>>N&&N)
    {
        for(int i=1; i<=N; i++)cin>>P[i].x>>P[i].y;
        if(N==2)//这道题的坑点 
        {
            cout<<setprecision(2)<<Length(P[1]-P[2])<<endl;
            continue;
        }
        int count=Andrew(N);//我的这个代码要是两个点的话，凸包是三个点。。。。。。 
        double ans=0;
        for(int i=1;i<count;i++)
        {
            ans+=Length(Convex[i]-Convex[i+1]);
        }
        if(count!=2)ans+=Length(Convex[1]-Convex[count]);
        cout<<setprecision(2)<<ans<<endl;
    }
}

hdu 1392 Surround the Trees（凸包裸题）

题目链接

Graham

①为什么要排个序喃？

②为什么要先找最下面最左边的点？

Andrew