Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. ifstream fin ("mosia1.in");
  5. ofstream fout ("mosia1.out");
  6. const int Nmax = 205;
  7. int n, st[Nmax], top;
  8. double dp[Nmax];
  9. struct P
  10. {
  11.  
  12. double ox, oy , dist;
  13. };
  14. P a[Nmax];
  15. bool viz[Nmax];
  16.  
  17.  
  18. inline bool CMP(const P A, const P B)
  19. {
  20. if(A . oy == B . oy)
  21. return A . ox < B . ox;
  22. return A . oy < B . oy;
  23. }
  24. inline double CHECK(int i, int j, int k)
  25. {
  26. return (a[i] . ox * a[j] . oy + a[i] . oy * a[k] . ox + a[j] . ox * a[k] . oy
  27. - a[k] . ox * a[j] . oy - a[j] . ox * a[i] . oy - a[i] . ox * a[k] . oy);
  28. }
  29. inline void Solve()
  30. {
  31. ++top;
  32. st[1] = 1;
  33. ++top;
  34. st[top] = 2;
  35. viz[2] = true;
  36. for(int i = 3 ; i <= n ; i++)
  37. {
  38. while(top > 1 && CHECK(st[top - 1], st[top], i) < 0)
  39. {
  40. viz[st[top]] = false;
  41. top--;
  42. }
  43. ++top;
  44. st[top] = i;
  45. viz[i] = true;
  46. }
  47. for(int i = n ; i >= 1 ; i--)
  48. if(!viz[i]) /// nu se afla in infasuratoare
  49. {
  50. while(top > 1 && CHECK(st[top - 1], st[top], i) < 0)
  51. {
  52. viz[st[top]] = false;
  53. top--;
  54. }
  55. ++top;
  56. st[top] = i;
  57. viz[i] = true;
  58. }
  59. top--;
  60. ///for(int i = 1 ; i <= top ; i++)
  61. ///fout << st[i] << " ";
  62. }
  63. inline double Dist(int i , int j)
  64. {
  65. return sqrt((a[j].ox - a[i] . ox) * (a[j].ox - a[i].ox) +
  66. (a[j].oy - a[i].oy) * (a[j].oy - a[i].oy));
  67. }
  68. inline void DP()
  69. {
  70. /// dp[i] = aria maxima obtinuta din primele i
  71. /// alegand obligatoriu punctul st[1]
  72. double sol;
  73. dp[1] = Dist(st[n] , st[2]) * a[st[1]].dist / 2;
  74. dp[2] = dp[1];
  75. for(int i = 3 ; i < n ; i++)
  76. {
  77. dp[i] = max(dp[i - 1] , dp[i - 2] + Dist(st[i - 1] , st[i + 1]) * a[st[i]].dist / 2);
  78. }
  79. sol = dp[n - 1];
  80. /// dp[i] = aria maxima obtinuta din primele i
  81. /// alegand obligatoriu punctul st[2]
  82. dp[1] = 0;
  83. dp[2] = Dist(st[1] , st[3]) * a[st[2]].dist / 2;
  84. for(int i = 3 ; i <= n ; i++)
  85. {
  86. dp[i] = max(dp[i - 1] , dp[i - 2] + Dist(st[i - 1] , st[i + 1]) * a[st[i]].dist / 2);
  87. }
  88. sol = max(sol , dp[n]);
  89. fout << fixed << setprecision(6) << sol << "\n";
  90. }
  91. int main()
  92. {
  93. fin >> n;
  94. for(int i = 1 ; i <= n ; i++)
  95. fin >> a[i] . ox >> a[i] . oy >> a[i] . dist;
  96. sort(a + 1, a + n + 1, CMP);
  97. Solve();
  98. DP();
  99. fin.close();
  100. fout.close();
  101. return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement