Advertisement
Guest User

Untitled

a guest
Apr 2nd, 2020
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.46 KB | None | 0 0
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace std;
  9. template <class T>
  10. using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  11. template <class T>
  12. using ordered_multiset = __gnu_pbds::tree<T, __gnu_pbds::null_type, less_equal<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  13.  
  14. #define PI atan2(0, -1)
  15. #define EPS 1e-9
  16. #define INF 5e18
  17. #define MOD 1000000007
  18.  
  19. #define mp make_pair
  20. #define pb push_back
  21. #define f first
  22. #define s second
  23. #define lb lower_bound
  24. #define ub upper_bound
  25.  
  26. int N;
  27. long double W, H, L, ret;
  28. vector<long double> places;
  29.  
  30. long double calcDist(long double l, long double r){ return (l*H/W+r*H/W+r-l)/2; }
  31.  
  32. long double calcCost(long double dist){ return 0.5*pow(dist, 2); }
  33.  
  34. int main(){
  35. //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
  36. ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
  37. cin >> W >> H >> N; L = W; ret = 2*calcCost(calcDist(0, L));
  38. //cout << ret << '\n';
  39. for(int iter = 0; iter < N; iter++){
  40. long double lo = 0, hi = L;
  41. for(int titer = 0; titer < 500 && lo+EPS < hi; titer++){
  42. long double t1 = (2*lo+hi)/3, t2 = (lo+2*hi)/3;
  43. long double t1cost = ret-2*calcCost(calcDist(0, L)), t2cost = t1cost;
  44. t1cost += 2*(calcCost(calcDist(0, t1))+calcCost(calcDist(t1, L)))-calcCost(t1*H/W);
  45. t2cost += 2*(calcCost(calcDist(0, t2))+calcCost(calcDist(t2, L)))-calcCost(t2*H/W);
  46. if(t1cost <= t2cost) hi = t2;
  47. else lo = t1;
  48. //cout << t1 << ' ' << t2 << endl;
  49. //cout << t1cost << ' ' << t2cost << endl;
  50. }
  51. long double pos = (lo+hi)/2;
  52. ret -= 2*calcCost(calcDist(0, L));
  53. ret += 2*(calcCost(calcDist(0, pos))+calcCost(calcDist(pos, L)))-calcCost(pos*H/W);
  54. places.pb(pos); L = pos;
  55. }
  56. cout << ret << '\n';
  57. reverse(places.begin(), places.end());
  58. for(int i = 0; i < min((int)places.size(), 10); i++) cout << places[i] << '\n';
  59. //cout << calcDist(0, 3) << ' ' << calcDist(3, W) << endl;
  60. return 0;
  61. }
  62.  
  63. /******************************
  64. Kateba ii dake no hanashi darou
  65. Success is only a victory away
  66. - No Game No Life Opening
  67. ******************************/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement