QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203367#2483. Roof Escapesalvator_noster#WA 1ms6340kbC++144.9kb2023-10-06 16:57:142023-10-06 16:57:14

Judging History

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

  • [2023-10-06 16:57:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6340kb
  • [2023-10-06 16:57:14]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int SIZE = 100000 + 5;
const double eps = 1e-9;

int sgn(double x) {
    if (x < -eps)
        return -1;
    if (x > eps)
        return 1;
    return 0;
}

bool Quadratic(double A, double B, double C, double *t0, double *t1) {
    double discrim = B * B - 4 * A * C;
    if (discrim < 0.)
        return false;
    double rootDiscrim = sqrt(discrim);
    double q;
    if (B < 0)
        q = -.5f * (B - rootDiscrim);
    else
        q = -.5f * (B + rootDiscrim);
    *t0 = q / A;
    *t1 = C / q;
    if (*t0 > *t1)
        swap(*t0, *t1);
    return true;
}

struct vec {
    double x, y;
    vec() {
        x = y = 0;
    }
    vec(double _x, double _y) {
        x = _x, y = _y;
    }
    vec operator+(vec v) {
        return vec(x + v.x, y + v.y);
    }
    vec operator-(vec v) {
        return vec(x - v.x, y - v.y);
    }
    vec operator*(double v) {
        return vec(x * v, y * v);
    }
    vec operator/(double v) {
        return vec(x / v, y / v);
    }
    double operator*(vec v) {
        return x * v.x + y * v.y;
    }
    double len() {
        return hypot(x, y);
    }
    double len_sqr() {
        return x * x + y * y;
    }
    vec rotate(double c) {
        return vec(x * cos(c) - y * sin(c), x * sin(c) + y * cos(c));
    }
    vec trunc(double l) {
        return (*this) * l / len();
    }
    vec rot90() {
        return vec(-y, x);
    }
};
double cross(vec a, vec b) {
    return a.x * b.y - a.y * b.x;
}
double get_angle(vec a, vec b) {
    return fabs(atan2(fabs(cross(a, b)), a * b));
}
vec lerp(vec a, vec b, double t) {
    return a * (1 - t) + b * t;
}
bool point_on_segment(vec p, vec a, vec b) {
    return sgn(cross(b - a, p - a)) == 0 && sgn((p - a) * (p - b)) <= 0;
}
int has_intersection(vec a, vec b, vec p, vec q) {
    int d1 = sgn(cross(b - a, p - a)), d2 = sgn(cross(b - a, q - a));
    int d3 = sgn(cross(q - p, a - p)), d4 = sgn(cross(q - p, b - p));
    if (d1 * d2 < 0 && d3 * d4 < 0) {
        return 1;
    }
    if ((d1 == 0 && point_on_segment(p, a, b)) ||
        (d2 == 0 && point_on_segment(q, a, b)) ||
        (d3 == 0 && point_on_segment(a, p, q)) ||
        (d4 == 0 && point_on_segment(b, p, q))) {
        return -1;
    }
    return 0;
}
int line_intersection(vec a, vec b, vec p, vec q, vec &o, double *t = 0) {
    double U = cross(p - a, q - p);
    double D = cross(b - a, q - p);
    if (sgn(D) == 0) {
        return sgn(U) == 0 ? 2 : 0;
    }
    o = a + (b - a) * (U / D);
    if (t)
        *t = U / D;
    return 1;
}

int w, h, n, m;
int stx, sty, edx, edy;
vector<int> mp[SIZE];
vector<double> path;

bool cmp(double a, double b) {
    return sgn(a - b) == 0;
}

int main(void) {
    scanf("%d%d%d%d%d%d", &w, &h, &stx, &sty, &edx, &edy);
    n = h / 2, m = w / 2;
    for (int i = 0; i <= n + 1; ++i) {
        mp[i].resize(m + 2);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &mp[i][j]);
        }
    }
    double ans = (vec(stx, sty) - vec(edx, edy)).len();
    vec st = vec(stx, sty), ed = vec(edx, edy);
    for (int i = 0; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            vec p = vec(i * 2, j * 2 - 2), q = vec(i * 2, j * 2);
            if (has_intersection(st, ed, p, q)) {
                double t;
                vec _;
                line_intersection(st, ed, p, q, _, &t);
                path.push_back(t);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            vec p = vec(i * 2 - 2, j * 2), q = vec(i * 2, j * 2);
            if (has_intersection(st, ed, p, q)) {
                double t;
                vec _;
                line_intersection(st, ed, p, q, _, &t);
                path.push_back(t);
            }
        }
    }
    path.push_back(0);
    path.push_back(1);
    sort(path.begin(), path.end());
    path.erase(unique(path.begin(), path.end(), cmp), path.end());
    int sz = path.size();
    // printf("path.size = %d\n", (int)path.size());
    // for (double num : path) {
    //     printf("num = %f\n", num);
    // }
    for (int i = 1; i < sz - 1; ++i) {
        vec p = lerp(st, ed, path[i - 1]), q = lerp(st, ed, path[i]),
            r = lerp(st, ed, path[i + 1]);
        vec a = (p + q) / 2, b = (q + r) / 2;
        int y1 = ceil(a.x / 2), x1 = ceil(a.y / 2);
        int y2 = ceil(b.x / 2), x2 = ceil(b.y / 2);
        // printf("(%d, %d), (%d, %d)\n", x1, y1, x2, y2);
        if (x1 == x2 || y1 == y2) {
            ans += abs(mp[x1][y1] - mp[x2][y2]);
        } else {
            int maxi =
                max(max(mp[x1][y1], mp[x2][y2]), min(mp[x2][y1], mp[x1][y2]));
            ans += abs(maxi - mp[x1][y1]) + abs(maxi - mp[x2][y2]);
        }
    }
    printf("%.10f\n", ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 26 1 1 3 25
0 1
0 5
5 5
0 1
2 1
4 1
5 0
0 0
1 0
6 4
3 2
5 4
1 5

output:

24.0831891576

result:

wrong answer 1st numbers differ - expected: '53.08319', found: '24.08319', error = '0.54631'