Областная олимпиада по информатике 2013-2014

При обработке изображений часто встречается такая задача, когда нужно изменить размер изображения так, чтобы оно “вписалось” в заданный прямоугольник. То есть исходное изображение уменьшается (или увеличивается) таким образом, что одна из его сторон становится точно равной соответствующей стороне заданного прямоугольника, а вторая сторона подбирается так, чтобы соотношение сторон получившегося изображения было как можно ближе к оригиналу. При этом размеры получившегося изображения должны быть наибольшими возможными, но не должны при этом превышать размеры прямоугольника. Также, все размеры должны быть целыми положительными числами.
Вам заданы размеры исходного изображения и размеры прямоугольника, в который это изображение нужно вписать. Вычислите, какими должны быть размеры вписанного изображения. Учтите, что поворачивать изображение или прямоугольник нельзя!

Входные данные

Входной файл содержит 4 целых числа $A$,$B$,$C$,$D$ ($1 ≤ A,B,C,D ≤ 10^9$), где $A$ и $B$ — ширина и высота исходного изображения, а $C$ и $D$ — ширина и высота прямоугольника, в который изображение нужно вписать.

Выходные данные

Выведите 2 целых числа: ширину и высоту обработанного изображения.

Примеры:

Вход:

1280 720 640 480

Ответ:

640 360

Вход:

640 480 1280 720

Ответ:

960 720

Оценивание:

В 50% тестов: A,B,C,D ≤ 1000 В 75% тестов: A, B, C, D ≤ 1000000

Комментарий/решение

zhezbil

Сам не писал контест + тут нет кнопки проверки. Надеюсь мое решение верно :)

показать/скрыть код

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ll long long

void solve() {
    int A, B, C, D;

    cin >> A >> B >> C >> D;

    double KW = (double)C / A;
    double KH = (double)D / B;

    int RW, RH;

    if (KW < KH) {
        RW = floor(A * KW);
        RH = floor(B * KW + 0.5);
    } else {
        RW = floor(A * KH + 0.5);
        RH = floor(B * KH);
    }

    cout << RW << " " << RH;
}

int main() {
    int tt = 1; // cin >> tt;
    while (tt--) {
        solve();
    }
}

C++

Copy

Проверял только на данных тестах и на одном своем, так что не гарантирую правильность.

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mxll LLONG_MAX
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
const int INF = 1e9;
const int mod = 1e9+7;

int main() {
    IOS;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    double r = (double) a/b, k = (double) c/d;
    ll g1 = gcd(a, b), g2 = gcd(c, d);
    a/=g1; b/=g1;
    if(r >= k) {
        cout << (c/a)*a << " " << (((c/a)*a)*b)/a;
    } else {
        cout << (((d/b)*b)*a)/b << " " << (d/b)*b;
    }
}

C++

Copy