Guest User

Untitled

a guest
Jul 22nd, 2016
354
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <string>
  7. #include <cstring>
  8. #include <cstdio>
  9. #include <set>
  10. #include <map>
  11. #include <unordered_map>
  12. #include <unordered_set>
  13. #include <ctime>
  14.  
  15. typedef long long ll;
  16. using namespace std;
  17.  
  18. int n;
  19. double mass[1000000];
  20.  
  21. long double find(long double first, long double razn)
  22. {
  23. long double res=0;
  24. for(int i=0;i<n;i++)
  25. {
  26. first+=razn;
  27. res+=(mass[i]-first)*(mass[i]-first);
  28. }
  29. return res;
  30. }
  31.  
  32. pair<long double,long double> solveFor(long double first)
  33. {
  34. long double l=-1e5, r=1e5;
  35. for(int i=0;i<70;i++)
  36. {
  37. long double mid1=l+(r-l)/3;
  38. long double mid2=l+(r-l)/3*2;
  39. long double res1=find(first,mid1);
  40. long double res2=find(first,mid2);
  41. if(res1<res2)
  42. r=mid2;
  43. else
  44. l=mid1;
  45. }
  46. return make_pair(find(first,l),l);
  47. }
  48.  
  49. pair<long double, long double> solve()
  50. {
  51. long double l=-1e10, r=1e10;
  52. for(int i=0;i<100;i++)
  53. {
  54. long double mid1=l+(r-l)/3;
  55. long double mid2=l+(r-l)/3*2;
  56. long double res1=solveFor(mid1).first;
  57. long double res2=solveFor(mid2).first;
  58. if(res1<res2)
  59. r=mid2;
  60. else
  61. l=mid1;
  62. }
  63. return make_pair(l,solveFor(l).second);
  64.  
  65. }
  66.  
  67. int main()
  68. {
  69. scanf("%d",&n);
  70. for(int i=0;i<n;i++)
  71. scanf("%lf",mass+i);
  72. printf("%.30lf %.30lf",(double)solve().first+(double)solve().second,(double)solve().second);
  73. }
Advertisement
Add Comment
Please, Sign In to add comment