QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#367872#8505. Almost Aligneducup-team1196#WA 6ms3816kbC++234.4kb2024-03-26 15:56:102024-03-26 15:56:11

Judging History

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

  • [2024-03-26 15:56:11]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3816kb
  • [2024-03-26 15:56:10]
  • 提交

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];
    }
    double l = 0, r = 1e18;
    auto get = [&](double mid) {
        double lx = 1e100, rx = -1e100;
        double ly = 1e100, ry = -1e100;
        for (int i = 1; i <= n; i++) {
            double xx = (double)x[i] + mid * dx[i];
            double yy = (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 = [&](double mid) {
        double lx = 1e100, rx = -1e100;
        for (int i = 1; i <= n; i++) {
            double xx = (double)x[i] + mid * dx[i];
            lx = std::min(lx, xx);
            rx = std::max(rx, xx);
        }
        return (rx - lx);
    };
    auto gety = [&](double mid) {
        double ly = 1e100, ry = -1e100;
        for (int i = 1; i <= n; i++) {
            double yy = (double)y[i] + mid * dy[i];
            ly = std::min(ly, yy);
            ry = std::max(ry, yy);
        }
        return (ry - ly);
    };
    double ret = 1e18;
    for(int d = 3; d <= 200; d++) {
        l = 0, r = 1e18;
        for (int i = 1; i <= 200; i++) {
            double m1 = l + (r - l) / d, m2 = l + (d - 1) * (r - l) / d;
            double ans1 = get(m1), ans2 = get(m2);
            if (ans1 < ans2) {
                r = m2;
            } else {
                l = m1;
            }
        }

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

        double ans2 = l;
        l = 0, r = 1e12;
        for (int i = 1; i <= 150; i++) {
            double m1 = l + (r - l) / d, m2 = l + (d - 1) * (r - l) / d;
            double ans1 = gety(m1), ans2 = gety(m2);
            if (ans1 < ans2) {
                r = m2;
            } else {
                l = m1;
            }
        }
        double ans3 = l;
        double MID = (ans2 + ans3) / 2;
        l = ans2, r = MID;
        for (int i = 1; i <= 150; i++) {
            double m1 = l + (r - l) / d, m2 = l + (d - 1) * (r - l) / d;
            double ans1 = get(m1), ans2 = get(m2);
            if (ans1 < ans2) {
                r = m2;
            } else {
                l = m1;
            }
        }
        double ans4 = l;
        l = MID, r = ans3;
        for (int i = 1; i <= 150; i++) {
            double m1 = l + (r - l) / d, m2 = l + (d - 1) * (r - l) / d;
            double ans1 = get(m1), ans2 = get(m2);
            if (ans1 < ans2) {
                r = m2;
            } else {
                l = m1;
            }
        }
        double ans5 = l;
        l = ans2, r = ans3;
        for (int i = 1; i <= 150; i++) {
            double m1 = l + (r - l) / d, m2 = l + (d - 1) * (r - l) / d;
            double ans1 = get(m1), ans2 = get(m2);
            if (ans1 < ans2) {
                r = m2;
            } else {
                l = m1;
            }
        }
        double ans6 = l;
        l = 0, r = ans2;
        for (int i = 1; i <= 150; i++) {
            double m1 = l + (r - l) / d, m2 = l + (d - 1) * (r - l) / d;
            double ans1 = get(m1), ans2 = get(m2);
            if (ans1 < ans2) {
                r = m2;
            } else {
                l = m1;
            }
        }
        double ans7 = l;
        l = ans2, r = 1e12;
        for (int i = 1; i <= 150; i++) {
            double m1 = l + (r - l) / d, m2 = l + (d - 1) * (r - l) / d;
            double ans1 = get(m1), ans2 = get(m2);
            if (ans1 < ans2) {
                r = m2;
            } else {
                l = m1;
            }
        }
        double ans8 = l;
        ret = std::min({ret, get(ans1), get(ans2), get(ans3), get(ans4), get(ans5), get(ans6), get(ans7), get(ans8)});
    }
    cout << ret << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 3816kb

input:

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

output:

22.2222

result:

wrong answer 1st numbers differ - expected: '22.2222222', found: '22.2222000', error = '0.0000010'