fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long double
  3.  
  4. using namespace std;
  5.  
  6. int x[561],y[561],n,k,r;
  7. ll dp[561][261];
  8. int maxy[561][561];
  9.  
  10. ll dist(double x1,double x2,double y1,double y2)
  11. {
  12.     return sqrt((abs(x2-x1)*abs(x2-x1))+(abs(y2-y1)*abs(y2-y1)));
  13. }
  14.  
  15. int main()
  16. {
  17.      cin>>n>>k>>r;
  18.      for(int i=1;i<=n;i++)
  19.      {
  20.          cin>>x[i]>>y[i];
  21.      }
  22.      for(int i=0;i<=k;i++)
  23.      {
  24.         dp[1][i]=0;
  25.         dp[2][i]=dist(x[1],x[2],y[1],y[2]);
  26.      }
  27.  
  28.  
  29.      for(int i=1;i<=n;i++)
  30.      {
  31.          maxy[i][i]=y[i];
  32.          for(int j=i+1;j<=n;j++)
  33.          {
  34.              maxy[i][j]=max(maxy[i][j-1],y[j]);
  35.          }
  36.      }
  37.  
  38.  
  39.      for(int i=3;i<=n;i++)
  40.      {
  41.          for(int j=0;j<=k;j++)
  42.          {
  43.              if(j==0)
  44.                 dp[i][j]=dist(x[i-1],x[i],y[i-1],y[i])+dp[i-1][j];
  45.              else
  46.              {
  47.                  dp[i][j]=dist(x[i-1],x[i],y[i-1],y[i])+dp[i-1][j];
  48.  
  49.                  for(int l=i-2;l>0;l--)
  50.                  {
  51.                     if(maxy[l+1][i-1]<=y[l] && maxy[l+1][i-1]<=y[i])
  52.                     {
  53.                         if(dist(x[l],x[i],y[l],y[i])<=r)
  54.                         {
  55.                             dp[i][j]=min(dp[i][j],dp[l][j-1]+dist(x[l],x[i],y[l],y[i]));
  56.                         }
  57.                     }
  58.                  }
  59.              }
  60.          }
  61.      }
  62.      cout<<fixed<<setprecision(6)<<dp[n][k];
  63. }
  64.  
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.000000
https://ideone.com/Qpq3b0
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!