Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<map>
- #include<vector>
- #include<stack>
- #include<algorithm>
- #include<cmath>
- #include<set>
- #include<iomanip>
- #include<fstream>
- using namespace std;
- ifstream in("frog.in");
- ofstream out("frog.out");
- bool check(vector<pair<long long, long long>> &v, long long w, long long h, long double k) {
- long double x = 0;
- long double y = 0;
- long double wi = 0, hi = 0;
- long long prev_h = -1;
- int last = -1;
- for(int i = 0; i < v.size(); i++) {
- wi = v[i].first * k;
- hi = v[i].second * k;
- if(prev_h == v[i].second) {
- if(x + wi <= w)
- x += wi;
- else {
- x = 0;
- y += hi;
- }
- last = 1;
- }
- else {
- x = wi;
- y += hi;
- last = 2;
- }
- prev_h = v[i].second;
- }
- return x <= w && y <= h;
- }
- int main() {
- long long n, w, h;
- cin >> n >> w >> h;
- vector<pair<long long, long long>> v(n);
- for(int i = 0; i < n; i++)
- cin >> v[i].first >> v[i].second;
- long double l = 0, r = 1e9;
- for(int k = 0; k < 100; k++) {
- long double m = (l + r) / 2.0;
- if(check(v, w, h, m))
- l = m;
- else
- r = m;
- }
- cout.precision(100);
- cout << l << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement