题解 P2742 【[USACO5.1]圈奶牛Fencing the Cows】

檀黎斗·神 · 2017-10-09 18:52:56 · 题解

一道凸包的模板题

直接用扫描法就可以

但是找最下面的点的时候不能用快排，因为会超时4个点

但是在每次输入的时候判断一下就可以了

代码细节也加了注释，直接上代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct node{
    double x,y;
}p[10005],s[10005];
int n;
double ans,mid;
double CJ(node a1,node a2,node b1,node b2)
{
    return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}//叉积大于0，则a左转后到b 
double dis(node p1,node p2)
{
    return sqrt( (double)(p2.y-p1.y)*(p2.y-p1.y)*1.0+(double)(p2.x-p1.x)*(p2.x-p1.x)*1.0 );
}//两点距离公式 
bool cmp(node p1,node p2)
{
    double tmp=CJ(p[1],p1,p[1],p2);
    if(tmp>0) return 1;
    if(tmp==0 && dis(p[0],p1)<dis(p[0],p2)) return 1;
    return 0;
}//按照夹角的大小排序 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(i!=1&&p[i].y<p[1].y)
        {
            mid=p[1].y;p[1].y=p[i].y;p[i].y=mid;
            mid=p[1].x;p[1].x=p[i].x;p[i].x=mid;
        }
    } 
    //init 

    sort(p+2,p+1+n,cmp);//按照夹角大小 
    s[1]=p[1];
    int tot=1;//因为最低点一定在凸包内 
    for(int i=2;i<=n;i++)
    {
        while(tot>1&&CJ(s[tot-1],s[tot],s[tot],p[i])<=0) tot--;
        tot++;
        s[tot]=p[i];
    }
    s[tot+1]=p[1];
    for(int i=1;i<=tot;i++) ans+=dis(s[i],s[i+1]);
    printf("%.2lf\n",ans);
    return 0;
}