P2116题解

Grisses · 2022-02-18 22:55:19 · 题解

题面

对于一堆平面上的点，如果要用一个一个多边形框住的话，周长最小的无疑是凸包了（这很好证明，三角形的任意两边之和大于第三边，所以凸的会优于凹的）。要距离所有城池至少 L，再加一段弧就行了，不难发现，所有的弧的圆心角都是多边形的外角，对于一个凸多边形，外角和为 360^{\circ}。即一个圆。

所有答案是凸包的周长加上半径为 L 的圆的周长。

代码：

  #include<bits/stdc++.h>
  #define db double
  using namespace std;
  int n,L,top=0;//投票表示栈顶
  db p=3.14159265358979323846;//求圆的周长需要Pi
  struct node{//存储点
      db x,y;
      node(){}
      node(int a,int b){x=a,y=b;}
      bool operator<(const node &t)const{//重载小于（最左最下的一个点）
          return y<t.y||(y==t.y&&x<t.x);
      }
      node operator-(const node &t)const{//重载减
          return node(x-t.x,y-t.y);
      }
  }a[200005],s[200005];//s是栈
  db ans,_x,_y;
  int CPr(node A,node B){
      return A.x*B.y-A.y*B.x;//向量叉积
  }
  db len(node A,node B){return sqrt(1.0*(A.x-B.x)*(A.x-B.x)+1.0*(A.y-B.y)*(A.y-B.y));}//求距离
  bool cmp(node A,node B){//以最左最下的点为极点，建立极坐标系，按极角从小到大排序，如果极角相同则按距离从小到大排序
      _x=CPr(A-a[1],B-a[1]);
      if(_x>0)return 1;
      if(_x==0)return len(A,a[1])<len(B,a[1]);
      return 0;
  }
  int main()
  {
      scanf("%d%d",&n,&L);
      for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
      sort(a+1,a+n+1);
      sort(a+2,a+n+1,cmp);
      s[++top]=a[1];
      s[++top]=a[2];
      for(int i=3;i<=n;i++){
          while(top>2&&CPr(s[top]-s[top-1],a[i]-s[top-1])<=0)top--;
          s[++top]=a[i];
      }//求凸包
      for(int i=1;i<=top;i++)ans+=len(s[i],s[i%top+1]);//求周长
      ans+=p*L*2;//加上圆的周长
      printf("%.0lf",ans);//输出
      return 0;
  }