CF1030D Vasya and Triangle

本文主要是介绍CF1030D Vasya and Triangle，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题链接

• 题意：在 \(1 \leqslant n \leqslant 1e9, 1\leqslant m \leqslant 1e9, 1 < k \leqslant 1e9\) 的情况下，构造出 \(1\leqslant x \leqslant n, 1 \leqslant y\leqslant m\) 同时三个点构成的三角形面积等于 \(\frac{n\times m}{k}\)。
• 题解：主要是当在抽象成 \(x\times y = \frac{n\times m}{2\times k}\) 的时候，只注意了枚举终点，但是最关键的是起点也可以，因为这是有两个限制，就是 \(x\) 和 \(y\) 都得同时满足条件，所以当 \(x\) 从 \(1\) 开始会令 \(y\) 不满足，遍历过多。
• 代码：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;
ll n, m, k;
    ll N;
bool check(ll x, ll y) {
    if (x > N || y > m)return 0;
    return 1;
}
void solve() {
    scanf("%lld%lld%lld", &n, &m, &k);
    N = n;
    n = 2 * n * m;
    if (n % k != 0) {
        cout << "NO\n";
        return;
    }
    n /= k;
    for (ll x = max(1ll, n/(max(N,m))); x * x <= n; x ++) {
        ll y = n/(x);
        if (n % x == 0 ) {
            if (!check(x, y)) {
                swap(x, y);
                if (check(x, y)) {
                    cout << "YES\n";
                    cout << "0 0\n";
                    cout << 0 <<  " " << y << endl;
                    cout << x << " " << 0 << endl;
                    return;
                } else swap(x, y);
            } else {
                cout << "YES\n";
                cout << "0 0\n";
                cout << 0 <<  " " << y << endl;
                cout << x << " " << 0 << endl;
                return;
            }
        }
    }
    cout << "NO\n";
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ll n = 1;
    while (n--) {
        solve();
    }
    return 0;
}

这篇关于CF1030D Vasya and Triangle的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！