QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203358 | #2483. Roof Escape | salvator_noster# | WA | 0ms | 6388kb | C++14 | 4.9kb | 2023-10-06 16:54:00 | 2023-10-06 16:54:00 |
Judging History
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[x1][y2]), max(mp[x2][y1], mp[x2][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: 0ms
memory: 6388kb
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:
34.0831891576
result:
wrong answer 1st numbers differ - expected: '53.08319', found: '34.08319', error = '0.35793'