Submission #3863475

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

int read()
{
  int x=0,f=1;
  char ch=getchar();
  while((ch<'0')||(ch>'9'))
    {
      if(ch=='-')
        {
          f=-f;
        }
      ch=getchar();
    }
  while((ch>='0')&&(ch<='9'))
    {
      x=x*10+ch-'0';
      ch=getchar();
    }
  return x*f;
}

const int maxn=200000;
const int maxv=99999999;
const double pi=acos(-1);
const double D=11.4159265358979323846264338328;
const double K=-4.2920367320510338076867830836;

struct point
{
  int x,y;

  bool operator <(const point &other) const
  {
    return x<other.x;
  }
};

int n,a[maxn+10],f[maxn+10],sx,sy,tx,ty;
point p[maxn+10];

int main()
{
  sx=read();
  sy=read();
  tx=read();
  ty=read();
  n=read();
  for(int i=1; i<=n; ++i)
    {
      p[i].x=read();
      p[i].y=read();
    }
  if(sx>tx)
    {
      std::swap(sx,tx);
      std::swap(sy,ty);
    }
  if(sy>ty)
    {
      sy=maxv-sy;
      ty=maxv-ty;
      for(int i=1; i<=n; ++i)
        {
          p[i].y=maxv-p[i].y;
        }
    }
  std::sort(p+1,p+n+1);
  int tot=0;
  for(int i=1; i<=n; ++i)
    {
      if((p[i].x>=sx)&&(p[i].y>=sy)&&(p[i].x<=tx)&&(p[i].y<=ty))
        {
          a[++tot]=p[i].y;
        }
    }
  int cnt=0;
  memset(f,63,sizeof f);
  for(int i=1; i<=tot; ++i)
    {
      int pos=std::lower_bound(f+1,f+cnt+1,a[i])-f;
      f[pos]=a[i];
      if(pos>cnt)
        {
          ++cnt;
        }
    }
  double ans=100.0*(tx-sx+ty-sy);
  if(cnt==std::min(tx-sx,ty-sy)+1)
    {
      ans+=(cnt-1)*K+D;
    }
  else
    {
      ans+=cnt*K;
    }
  printf("%.15lf\n",ans);
  return 0;
}

Submission Info

Judge Result