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

· · 题解

方法是一样的，先求凸包，再算距离。但是我的程序比一般的有点不同。在算凸包时，我选择计算两点间角度差再做比较（就是下面的sita），其他地方基本与标程一样。这样算的话挺好理解的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const double Pi=3.1415926535898;
const int MAXN=10000+100;
bool nf[MAXN];
int n,c[MAXN];
struct cow
{
    double x,y;
}a[MAXN];//存牛的坐标
double sita(double x,double y)//计算角度，用的是弧度制，注意负角的处理
{
    double rou=sqrt(x*x+y*y);
    x/=rou;
    y/=rou;
    double s=acos(x);
    if(y>=0)return s;
    else return -s;
}
bool cmp(cow a,cow b)//sort函数比较
{
    return a.x<b.x||a.x==b.x&&a.y<b.y;
}
double dis(int x,int y)//求距离
{
    return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    int f=1;
    c[1]=1;
    int h=1,next;
    double angle;
    while(h!=n)
    {
        angle=3*Pi;
        next=0;
        for(int i=h+1;i<=n;i++)if(sita(a[i].x-a[h].x,a[i].y-a[h].y)<angle)//循环找倾斜角最小的边（倾斜角可为负数，虽然不严谨）
        {
            angle=sita(a[i].x-a[h].x,a[i].y-a[h].y);
            next=i;
        }
        c[++f]=next;
        nf[next]=true;
        h=next;
    }
    while(h!=1)//反过来再求一遍凸包
    {
        angle=3*Pi;
        next=0;
        for(int i=h-1;i>=1;i--)if(!nf[i]&&sita(a[h].x-a[i].x,a[h].y-a[i].y)<angle)
        {
            angle=sita(a[h].x-a[i].x,a[h].y-a[i].y);
            next=i;
        }
        c[++f]=next;
        h=next;
    }
    double sum=0.0;
    for(int i=1;i<f;i++)sum+=dis(c[i],c[i+1]);//求距离
    printf("%.2lf\n",sum);
    return 0;
}