QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353690#6426. Interested in SkiingPorNPtreeWA 1ms3904kbC++142.4kb2024-03-14 14:56:312024-03-14 14:56:31

Judging History

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

  • [2024-03-14 14:56:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3904kb
  • [2024-03-14 14:56:31]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int n, a[N], b[N], c[N], d[N];
pair<int, int> pr[N * 2];
double f[N * 2];
mt19937 rnd;

int ins(double a, double b, double c, double d, double e, double f, double g, double h)
{
    a += (double)rnd() / 1e18, b += (double)rnd() / 1e18, c += (double)rnd() / 1e18, d += (double)rnd() / 1e18;
    e += (double)rnd() / 1e18, f += (double)rnd() / 1e18, g += (double)rnd() / 1e18, h += (double)rnd() / 1e18;
    double k1 = (d - b) / (c - a), b1 = b - k1 * a;
    double k2 = (h - f) / (g - e), b2 = f - k2 * e;
    double ix = (b2 - b1) / (k1 - k2), iy = k1 * ix + b1;
    return ix > min(a, c) - 1e-4 && ix < max(a, c) + 1e-4 && ix > min(e, g) - 1e-4 && ix < max(e, g) + 1e-4 && iy > min(b, d) - 1e-4 && iy < max(b, d) + 1e-4 && iy > min(f, h) - 1e-4 && iy < max(f, h) + 1e-4 && fabs(ix - a) + fabs(iy - b) > 1e-4 && fabs(ix - c) + fabs(iy - d) > 1e-4 && fabs(ix - e) + fabs(iy - f) > 1e-4 && fabs(ix - g) + fabs(iy - h) > 1e-4;
}

int check(double a, double b, double c, double d)
{
    for (int i = 1; i <= n; ++i) {
        if (ins(a, b, c, d, ::a[i], ::b[i], ::c[i], ::d[i])) {
            return 0;
        }
    }
    return 1;
}

signed main()
{
    int m, V;
    scanf("%d%d%d", &n, &m, &V);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
        pr[i * 2 - 1] = make_pair(b[i], a[i]);
        pr[i * 2] = make_pair(d[i], c[i]);
    }
    sort(pr + 1, pr + n + n + 1);
    if (check(0, -20000, 0, 20000)) {
        puts("0");
        return 0;
    }
    double res = 1e10;
    for (int i = 1; i <= n + n; ++i) {
        f[i] = 1e10;
        if (pr[i].second <= -m || pr[i].second >= m) {
            continue;
        }
        if (check(pr[i].second, -20000, pr[i].second, pr[i].first)) {
            f[i] = 0;
        } else {
            for (int j = 1; j < i; ++j) {
                if (pr[i].first != pr[j].first && check(pr[j].second, pr[j].first, pr[i].second, pr[i].first)) {
                    f[i] = min(f[i], max(f[j], fabs((double)(pr[i].second - pr[j].second) / (pr[i].first - pr[j].first))));
                }
            }
        }
        if (check(pr[i].second, pr[i].first, pr[i].second, 20000)) {
            res = min(res, f[i]);
        }
    }
    if (res > 5e9) {
        puts("-1");
    } else {
        printf("%.10lf\n", res * V);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3904kb

input:

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

output:

0.0000000000

result:

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