Wall

任腾发表于 2007-08-09 16:23:02

    1.  /*
    2.  Northeastern Europe 2001
    3.  PKU1113
    4.  Wall
    5.  Author: Teng Ren
    6.  ~!~
    7.  */
    8.  #include <cstdio>
    9.  #include <string>
   10.  #include <cmath>
   11.  #include <algorithm>
   12.  #define maxn 1001
   13.  #define eps 1e-8
   14.  #define sqr(x) ((x)*(x))
   15.  using namespace std;
   16.  int n,m;
   17.  double L;
   18.
   19.  int dcmp(double x){
   20.    return x<-eps?-1:x>eps;
   21.  }
   22.
   23.  struct point{
   24.    double x,y;
   25.  }p[maxn],ch[maxn];
   26.
   27.  bool cmp(const point &a,const point &b){
   28.    return dcmp(a.x-b.x)<0||dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)<0;
   29.  }
   30.
   31.  double cross(point &a,point &b,point &c){
   32.    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
   33.  }
   34.
   35.  void getch(){
   36.    m=0;
   37.    for (int i=0;i<n;i++){
   38.      while (m>1&&dcmp(cross(ch[m-2],ch[m-1],p[i]))<0) m--;
   39.      ch[m++]=p[i];
   40.    }
   41.    for (int i=n-2;i>=0;i--){
   42.      while (m>1&&dcmp(cross(ch[m-2],ch[m-1],p[i]))<0) m--;
   43.      ch[m++]=p[i];
   44.    }
   45.  }
   46.
   47.  int main(){
   48.    scanf("%d%lf",&n,&L);
   49.    for (int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
   50.    double ans;
   51.    sort(p,p+n,cmp);
   52.    getch();
   53.    ans=2*acos(-1.0)*L;
   54.    for (int i=0;i+1<m;i++)
   55.      ans+=sqrt(sqr(ch[i].x-ch[i+1].x)+sqr(ch[i].y-ch[i+1].y));
   56.    printf("%.0lf\n",ans);
   57.    return 0;
   58.  }

关键词(Tag): c++ algorithm code 计算几何凸包 neerc

发表评论

* 昵称
	已经注册过? 请登录新用户请先注册以便能显示头像及追踪评论回复
Email
网址
* 评论
表情
* 验证码	请输入您看到的数字 (注册登录就不用每次输入讨厌的验证码了)