Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize ("O3")
- #pragma GCC target ("sse4")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- template <class T>
- 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>;
- template <class T>
- 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>;
- #define PI atan2(0, -1)
- #define EPS 1e-9
- #define INF 5e18
- #define MOD 1000000007
- #define mp make_pair
- #define pb push_back
- #define f first
- #define s second
- #define lb lower_bound
- #define ub upper_bound
- int N;
- long double W, H, L, ret;
- vector<long double> places;
- long double calcDist(long double l, long double r){ return (l*H/W+r*H/W+r-l)/2; }
- long double calcCost(long double dist){ return 0.5*pow(dist, 2); }
- int main(){
- //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
- ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
- cin >> W >> H >> N; L = W; ret = 2*calcCost(calcDist(0, L));
- //cout << ret << '\n';
- for(int iter = 0; iter < N; iter++){
- long double lo = 0, hi = L;
- for(int titer = 0; titer < 500 && lo+EPS < hi; titer++){
- long double t1 = (2*lo+hi)/3, t2 = (lo+2*hi)/3;
- long double t1cost = ret-2*calcCost(calcDist(0, L)), t2cost = t1cost;
- t1cost += 2*(calcCost(calcDist(0, t1))+calcCost(calcDist(t1, L)))-calcCost(t1*H/W);
- t2cost += 2*(calcCost(calcDist(0, t2))+calcCost(calcDist(t2, L)))-calcCost(t2*H/W);
- if(t1cost <= t2cost) hi = t2;
- else lo = t1;
- //cout << t1 << ' ' << t2 << endl;
- //cout << t1cost << ' ' << t2cost << endl;
- }
- long double pos = (lo+hi)/2;
- ret -= 2*calcCost(calcDist(0, L));
- ret += 2*(calcCost(calcDist(0, pos))+calcCost(calcDist(pos, L)))-calcCost(pos*H/W);
- places.pb(pos); L = pos;
- }
- cout << ret << '\n';
- reverse(places.begin(), places.end());
- for(int i = 0; i < min((int)places.size(), 10); i++) cout << places[i] << '\n';
- //cout << calcDist(0, 3) << ' ' << calcDist(3, W) << endl;
- return 0;
- }
- /******************************
- Kateba ii dake no hanashi darou
- Success is only a victory away
- - No Game No Life Opening
- ******************************/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement