QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#367856	#8505. Almost Aligned	ucup-team1196^#	WA	0ms	3816kb	C++23	3.2kb	2024-03-26 15:37:23	2024-03-26 15:37:23

Judging History

你现在查看的是最新测评结果

[2024-03-26 15:37:23]
评测

测评结果：WA
用时：0ms
内存：3816kb

查看

[2024-03-26 15:37:23]
提交

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    std::cin >> n;
    std::vector<int> x(n + 1), y(n + 1), dx(n + 1), dy(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> x[i] >> y[i] >> dx[i] >> dy[i];
    }
    long double l = 0, r = 1e18;
    auto get = [&](long double mid) {
        long double lx = 1e100, rx = -1e100;
        long double ly = 1e100, ry = -1e100;
        for (int i = 1; i <= n; i++) {
            long double xx = (long double)x[i] + mid * dx[i];
            long double yy = (long double)y[i] + mid * dy[i];
            lx = std::min(lx, xx);
            rx = std::max(rx, xx);
            ly = std::min(ly, yy);
            ry = std::max(ry, yy);
        }
        return (rx - lx) * (ry - ly);
    };
    auto getx = [&](long double mid) {
        long double lx = 1e100, rx = -1e100;
        for (int i = 1; i <= n; i++) {
            long double xx = (long double)x[i] + mid * dx[i];
            lx = std::min(lx, xx);
            rx = std::max(rx, xx);
        }
        return (rx - lx);
    };
    auto gety = [&](long double mid) {
        long double ly = 1e100, ry = -1e100;
        for (int i = 1; i <= n; i++) {
            long double yy = (long double)y[i] + mid * dy[i];
            ly = std::min(ly, yy);
            ry = std::max(ry, yy);
        }
        return (ry - ly);
    };
    l = 0, r = 1e18;
    for (int i = 1; i <= 150; i++) {
        long double m1 = l + (r - l) / 3, m2 = l + 2 * (r - l) / 3;
        long double ans1 = get(m1), ans2 = get(m2);
        if (ans1 < ans2) {
            r = m2;
        } else {
            l = m1;
        }
    }

    long double ans1 = l;
    l = 0, r = 1e18;
    for (int i = 1; i <= 150; i++) {
        long double m1 = l + (r - l) / 3, m2 = l + 2 * (r - l) / 3;
        long double ans1 = getx(m1), ans2 = getx(m2);
        if (ans1 < ans2) {
            r = m2;
        } else {
            l = m1;
        }
    }

    long double ans2 = l;
    l = 0, r = 1e18;
    for (int i = 1; i <= 150; i++) {
        long double m1 = l + (r - l) / 3, m2 = l + 2 * (r - l) / 3;
        long double ans1 = gety(m1), ans2 = gety(m2);
        if (ans1 < ans2) {
            r = m2;
        } else {
            l = m1;
        }
    }
    long double ans3 = l;
    long double MID = (ans2 + ans3) / 2;
    l = ans2, r = MID;
    for (int i = 1; i <= 150; i++) {
        long double m1 = l + (r - l) / 3, m2 = l + 2 * (r - l) / 3;
        long double ans1 = get(m1), ans2 = get(m2);
        if (ans1 < ans2) {
            r = m2;
        } else {
            l = m1;
        }
    }
    long double ans4 = l;
    l = MID, r = ans3;
    for (int i = 1; i <= 150; i++) {
        long double m1 = l + (r - l) / 3, m2 = l + 2 * (r - l) / 3;
        long double ans1 = get(m1), ans2 = get(m2);
        if (ans1 < ans2) {
            r = m2;
        } else {
            l = m1;
        }
    }
    long double ans5 = l;
    std::cout << std::fixed << std::setprecision(20) << std::min({get(ans1), get(ans2), get(ans3), get(ans4), get(ans5)}) << "\n";
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3808kb

input:

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0

output:

22.22222222222222222203

result:

ok found '22.222222222', expected '22.222222222', error '0.000000000'

Test #2:

score: -100

Wrong Answer

time: 0ms

memory: 3816kb

input:

output:

0.00000001103634923137

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '0.0000000', error = '0.0000000'