Guest User

Untitled

a guest
Dec 15th, 2019
81
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <cmath>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. ifstream f("discuri.in");
  8. ofstream g("discuri.out");
  9.  
  10. int n,i,j;
  11. long double r[10001], poz[10001];
  12. long double maxim, paux, distmax;
  13. int pmax;
  14. bool t;
  15.  
  16. int nrez, rez[10001];
  17. bool u[10001];
  18.  
  19. int main()
  20. {
  21. f>>n;
  22. f>>r[1];
  23. poz[1]=r[1];
  24. for (i=2;i<=n;i++)
  25. {
  26. f>>r[i];
  27. if (r[i]<r[i-1])
  28. poz[i]=poz[i-1]+2*sqrt(r[i]*r[i-1]);
  29. else if (r[i]==r[i-1])
  30. poz[i]=poz[i-1]+2*r[i];
  31. else
  32. {
  33. maxim=pmax=paux=0;
  34. t=0;
  35. for (j=i-1;j>=1 && t==0;j--)
  36. if (r[j]>maxim)
  37. {
  38. maxim=r[j];
  39. pmax=j;
  40. paux=poz[j]+2*sqrt(r[i]*r[j]);
  41. t=1;
  42. }
  43. for (j=pmax-1;j>=1;j--)
  44. if (r[j]>maxim)
  45. {
  46. maxim=r[j];
  47. if (sqrt((poz[j]-paux)*(poz[j]-paux) + (r[j]-r[i])*(r[j]-r[i])) < r[i]+r[j])
  48. {
  49. paux=poz[j]+2*sqrt(r[i]*r[j]);
  50. pmax=j;
  51. }
  52. }
  53.  
  54. if (paux<r[i])
  55. {
  56. paux=r[i];
  57. pmax=0;
  58. }
  59.  
  60. for (j=pmax+1;j<i;j++)
  61. if (!u[j])
  62. {
  63. nrez++;
  64. rez[nrez]=j;
  65. u[j]=1;
  66. }
  67.  
  68. poz[i]=paux;
  69. }
  70. distmax=max(distmax,poz[i]+r[i]);
  71. }
  72.  
  73. for (i=n;i>=1 && poz[i]+r[i]<distmax;i--)
  74. if (!u[i])
  75. {
  76. nrez++;
  77. rez[nrez]=i;
  78. u[i]=1;
  79. }
  80.  
  81. sort(rez+1,rez+nrez+1);
  82.  
  83. g<<nrez<<"\n";
  84. for (i=1;i<=nrez;i++)
  85. g<<rez[i]<<"\n";
  86.  
  87. return 0;
  88. }
RAW Paste Data