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

kczno1 · 2017-01-05 19:02:43 · 题解

来展示一下我的凸包模板。

我用的是水平序+栈

1 按x坐标为第一关键字,y坐标为第二关键字从小到大排序

2 从左到右枚举点，如果当前点相对于前面两个是向外的，就不断让栈顶出去。之后把点加入栈中。从而得到下凸包。

3 从右到左再做一遍。

#include<cstdio>
#include<cmath>
#include<algorithm> 
using namespace std;

#define oo 1000000
#define N 10100
double sqr(const double &x) { return x*x; }
struct point
{ double x,y;
  void read() { scanf("%lf%lf",&x,&y); }
  bool operator <(const point &i)const
  {
       return x<i.x||x==i.x&&y<i.y;
  }
  point operator -(const point &i)const
  {
      return (point){x-i.x,y-i.y};
  }
  double operator *(const point &i)const//叉积 得到当前方向是向左还是向右
  {
      return x*i.y-y*i.x;
  }
  friend double dis(const point &i,const point &j)
  {
      return sqrt(sqr(j.x-i.x)+sqr(j.y-i.y));
  }
}p[N],now;

int n,i;
point q[N];int top;
void push(const point &now)
{
   while ((now-q[top-1])*(q[top]-q[top-1])>0) --top;//当前点相对前面两个在外
   q[++top]=now; 
}
void tu()
{
        q[0]=q[top=1]=p[1];//设置哨点
        for (i=2;i<=n;++i) push(p[i]);
        for (i=n-1;i;--i) push(p[i]);//这时已有的点已经可以充当哨点了
}

double len()
{
    double ans=0;
    for (i=1;i<top;++i) ans+=dis(q[i],q[i+1]);
    return ans;
}

int main()
{
    //freopen("1.in","r",stdin);
    scanf("%d",&n);
    for (i=1;i<=n;++i) p[i].read();
    sort(p+1,p+n+1);
    tu();
    printf("%.2lf",len()); 
}