Advertisement
Guest User

Untitled

a guest
Sep 24th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<map>
  3. #include<vector>
  4. #include<stack>
  5. #include<algorithm>
  6. #include<cmath>
  7. #include<set>
  8. #include<iomanip>
  9. #include<fstream>
  10.  
  11. using namespace std;
  12.  
  13. ifstream in("frog.in");
  14. ofstream out("frog.out");
  15.  
  16. bool check(vector<pair<long long, long long>> &v, long long w, long long h, long double k) {
  17.     long double x = 0;
  18.     long double y = 0;
  19.     long double wi = 0, hi = 0;
  20.     long long prev_h = -1;
  21.     int last = -1;
  22.    
  23.     for(int i = 0; i < v.size(); i++) {
  24.         wi = v[i].first * k;
  25.         hi = v[i].second * k;
  26.         if(prev_h == v[i].second) {
  27.             if(x + wi <= w)
  28.                 x += wi;
  29.             else {
  30.                 x = 0;
  31.                 y += hi;
  32.             }
  33.             last = 1;
  34.         }
  35.         else {
  36.             x = wi;
  37.             y += hi;
  38.             last = 2;
  39.         }
  40.        
  41.         prev_h = v[i].second;
  42.     }
  43.    
  44.     return x <= w && y <= h;
  45. }
  46.  
  47. int main() {
  48.     long long n, w, h;
  49.     cin >> n >> w >> h;
  50.    
  51.     vector<pair<long long, long long>> v(n);
  52.     for(int i = 0; i < n; i++)
  53.         cin >> v[i].first >> v[i].second;
  54.    
  55.     long double l = 0, r = 1e9;
  56.     for(int k = 0; k < 100; k++) {
  57.         long double m = (l + r) / 2.0;
  58.        
  59.         if(check(v, w, h, m))
  60.             l = m;
  61.         else
  62.             r = m;
  63.     }
  64.    
  65.     cout.precision(100);
  66.     cout << l << endl;
  67.    
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement