fork(3) download
copy 
  1. #include<iostream>
  2. #include<math.h>
  3. #include<algorithm>
  4. #include <fstream>
  5. using namespace std;
  6. long double distanc(long double x, long double y, long double x1, long double y1)
  7. {
  8. 	long double difference_x=(x-x1)*1.0;
  9. 	long double difference_y=(y-y1)*1.0;
  10. 	// cout<<fixed;
  11. 	// cout.precision(6);
  12. 	long double ans= sqrt((difference_x*difference_x)+(difference_y*difference_y));
  13. 	return ans;
  14. }
  15.  
  16. long double maximum_happiness(long double *x, long double *y, long double *f, int *v, int n, long double happiness, int i, long double prevx, long double prevy)
  17. {
  18. 	if(i>n)
  19.         return 0.0;
  20.  
  21.     long double distance = distanc(prevx, prevy, x[i], y[i]);
  22.   //   cout<<distance<<"\n";
  23.     long double ans1{0},ans2{0};
  24.  
  25.     ans1 += maximum_happiness(x,y,f,v,n,happiness-distance+f[i],i+1,x[i],y[i]) + (f[i] - distance);
  26.  
  27.     ans2 += maximum_happiness(x,y,f,v,n,happiness,i+1,prevx,prevy);
  28.  
  29.     cout<<fixed;
  30. 	cout.precision(6);
  31.    //cout<<ans1<<" "<<ans2<<"\n";
  32.  
  33.     if(ans1>ans2)
  34.     {
  35.     	v[i] = 1;
  36.         return ans1;
  37.     }
  38.     else
  39.     {
  40.         return ans2;
  41.     }
  42. } 
  43.  
  44.  
  45. int main()
  46. {
  47. 	int n;
  48. 	cin>>n;
  49. 	long double *x=new long double [n];
  50. 	long double *y=new long double [n];
  51. 	long double *f=new long double [n];
  52.     int *v=new int [n];
  53.  
  54. 	for(int i=0; i<n; i++)
  55. 	{
  56. 		cin>>x[i]>>y[i]>>f[i];
  57.         v[i] = 0;
  58. 	}
  59.     cout<<fixed;
  60. 	cout.precision(6);
  61.     long double happiness;
  62.     v[0] = 1;
  63. 	long double ans = maximum_happiness(x, y, f, v, n-2, happiness,1,x[0],y[0]);
  64.  
  65.     long double x1,y1;
  66.     int i;
  67.  
  68.     for(i=(n-2) ; i>=0 ; i--)
  69.     {
  70.         if(v[i]==1)
  71.             break;
  72.     }
  73.  
  74.     x1 = x[i];
  75.     y1 = y[i];
  76.  
  77.     long double d = distanc(x1,y1,x[n-1],y[n-1]);
  78.  
  79.    // cout<<d<<"\n";
  80.     happiness = ans - d + f[n-1] + f[0];
  81.     cout<<happiness;
  82.  
  83.  
  84. 	delete[]x;
  85. 	delete[]y;
  86. 	delete[]f;
  87. }
  88.  
Success #stdin #stdout 0s 4544KB
comments (?)
stdin
copy 
3
0 0 1
3 1 4
6 0 9
stdout
copy 
7.675445
https://ideone.com/ZB2vV6
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!