QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#367859#8505. Almost Aligneducup-team1196#TL 0ms4068kbC++233.2kb2024-03-26 15:40:012024-03-26 15:40:03

Judging History

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

  • [2024-03-26 15:40:03]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4068kb
  • [2024-03-26 15:40:01]
  • 提交

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 <= 200; 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 <= 200; 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 <= 200; 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 <= 200; 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 <= 200; 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";
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3804kb

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: 0
Accepted
time: 0ms
memory: 3820kb

input:

3
0 -1 0 2
1 1 1 1
-1 1 -1 1

output:

0.00000000000000001821

result:

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

Test #3:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

3
0 -1 0 -2
1 1 1 1
-1 1 -1 1

output:

4.00000000000000000000

result:

ok found '4.000000000', expected '4.000000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

1
0 0 0 0

output:

0.00000000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4068kb

input:

4
1000000 1000000 -1 -1000000
1000000 -1000000 -1000000 1
-1000000 -1000000 1 1000000
-1000000 1000000 1000000 -1

output:

3999984000031.99995207786560058594

result:

ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'

Test #6:

score: -100
Time Limit Exceeded

input:

1000000
-871226 486657 -467526 31395
-65837 846554 469710 -907814
927993 -45099 713462 -276539
261942 483255 746021 811070
63449 -779486 588838 -413687
812070 -87868 -813499 -420768
112521 -622607 -832012 921368
-182120 517379 -401743 -837524
-685985 337832 643014 135144
12895 326935 -495720 930620
...

output:


result: