Advertisement
Guest User

Untitled

a guest
Jan 6th, 2016
281
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.08 KB | None | 0 0
  1. /*
  2. Bismillahir Rahmanir Rahim
  3. Farsid
  4. BUET
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define SET(a, x) memset((a), (x), sizeof(a))
  11. #define ll long long
  12. #define pb push_back
  13. #define mp make_pair
  14. #define all(x) (x).begin(),(x).end()
  15. #define SZ(x) ((int)(x).size())
  16. #define i64 ll
  17. #define IN(A, B, C) ((B) <= (A) && (A) <= (C))
  18. #define MAX
  19. #define xx first
  20. #define yy second
  21.  
  22. typedef vector<int> VI;
  23. typedef vector<string> VS;
  24. typedef vector<double> VD;
  25. typedef vector<ll> VL;
  26. typedef pair<int,int> PII;
  27. typedef pair<ll,ll> PLL;
  28. const int inf=0x20202020;
  29. const ll linf=(((i64)1)<<60)-1;
  30. const ll mod=1000000007;
  31. const double eps=1e-9;
  32. const double pi=3.1415926535897932384626;
  33.  
  34. const int DX[]={1,0,-1,0},DY[]={0,1,0,-1};
  35. ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  36. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
  37. ll inv_mod(ll a,ll mod){return powmod(a,mod-2,mod);}
  38.  
  39. void print(double n)
  40. {
  41. printf("%.9lf\n",n);
  42. //cout<<n<<endl;
  43.  
  44. }
  45.  
  46. double A[200009];
  47. int n;
  48.  
  49. double f(double x)
  50. {
  51. double ans=0,pos=0,neg=0;
  52. for(int i=0;i<n;i++){
  53. double a=A[i]-x;
  54. ans=max(ans,abs(a));
  55. pos+=a;
  56. if(pos<0)pos=0;
  57. neg+=a;
  58. if(neg>0)neg=0;
  59. ans=max(ans,pos);
  60. ans=max(ans,abs(neg));
  61. }
  62. return ans;
  63. }
  64.  
  65. double t_search(double lo, double hi)
  66. {
  67. double md1,md2,ans;
  68. for(int i=0;i<300;i++){
  69. md1=lo+(hi-lo)/3.0;
  70. md2=lo+(2*(hi-lo))/3.0;
  71. double a1=f(md1),a2=f(md2);
  72. if(a2<a1){
  73. lo=md1;
  74. ans=a2;
  75. }
  76. else{
  77. hi=md2;
  78. ans=a1;
  79. }
  80. }
  81. return ans;
  82. }
  83.  
  84. int main()
  85. {
  86. //freopen("far.in","r",stdin);
  87. //freopen("gadha.out","w",stdout);
  88. int i,j,k ,T,cas=0;
  89. //scanf("%d",&T);
  90. cin>>n;
  91. double mn=inf,mx=-inf;
  92. for(i=0;i<n;i++){
  93. cin>>A[i];
  94. mn=min(mn,A[i]);
  95. mx=max(mx,A[i]);
  96. }
  97. double ans=t_search(mn-10,mx+10);
  98. print(ans);
  99. return 0;
  100. }
  101. /*Test Cases
  102.  
  103.  
  104. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement