QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94774 | #5605. A-Mazing Puzzle | PetroTarnavskyi# | WA | 2ms | 3532kb | C++17 | 3.1kb | 2023-04-07 18:14:55 | 2023-04-07 18:14:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const double EPS = 1e-9;
struct Point {
double x, y;
Point() {}
Point(double _x, double _y): x(_x), y(_y) {}
Point operator-(const Point& p) const {
return {x - p.x, y - p.y};
}
double operator*(const Point& p) const {
return x * p.y - p.x * y;
}
double d2() const {
return x * x + y * y;
}
double len() const {
return sqrt(d2());
}
};
struct Line {
Point n;
double c;
Line() {}
Line(const Point& a, const Point& b) {
double A = b.y - a.y;
double B = a.x - b.x;
double C = -a.x * A - a.y * B;
n = Point(A, B);
c = C;
}
bool parallel (const Line& l) const {
return abs(n * l.n) < EPS;
}
Point intersect(const Line& l) const {
double z = n * l.n;
double x = -(c * l.n.y - n.y * l.c) / z;
double y = -(n.x * l.c - c * l.n.x) / z;
return Point(x, y);
}
};
int n;
vector<Point> p;
int findPointAbove(const Point& p1, const Point& p2, double l, double r) {
FOR(i, 0, n) {
if (p[i].x > l && p[i].x < r && (p2 - p1) * (p[i] - p1) > 0) {
return i;
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
cin >> n;
p.resize(n + 1);
for (Point& pi : p) {
cin >> pi.x >> pi.y;
}
Point c, s;
double r, dx, dy, v;
cin >> c.x >> s.x >> s.y >> r >> dx >> dy >> v;
double coef = v / sqrt(dx * dx + dy * dy);
dx *= coef;
dy *= coef;
FOR(i, 0, n) {
if (c.x > p[i].x - EPS && c.x < p[i + 1].x + EPS) {
c.y = p[i].y + (p[i + 1].y - p[i].y)
* (c.x - p[i].x) / (p[i + 1].x - p[i].x);
break;
}
}
double t = 1e18;
FOR(it, 0, 2) {
Line traj(s, Point(s.x + dx, s.y + dy));
FOR(i, 0, n) {
if (p[i].x < c.x + EPS) {
continue;
}
int j = findPointAbove(c, p[i], p[i].x, 1e4);
Line l(c, p[i]);
Point q;
if (j != -1) {
assert(j > 0);
q = l.intersect(Line(p[j - 1], p[j]));
}
Point touch = traj.intersect(l);
if (touch.x > p[i].x - EPS && (j == -1 || touch.x < q.x)) {
t = min(t, ((touch - s).len() - r) / v);
}
if (j != -1) {
double a = v * v;
double b = 2 * ((s.x - q.x) * dx + (s.y - q.y) * dy);
double cc = (s - q).d2() - r * r;
double D = b * b - 4 * a * cc;
if (D >= 0) {
double cur = (-b - sqrt(D)) / (2 * a);
if (cur > 0) {
t = min(t, cur);
}
}
}
}
FOR(i, 0, n) {
Line l(p[i], p[i + 1]);
if (traj.parallel(l)) {
continue;
}
Point q = traj.intersect(l);
if (q.x > c.x && findPointAbove(c, q, c.x, q.x) == -1) {
t = min(r, ((q - s).len() - r) / v);
}
}
for (Point& pi : p) {
pi.x *= -1;
}
c.x *= -1;
s.x *= -1;
dx *= -1;
}
if (t > 1e17) {
cout << "-1\n";
}
else {
cout << t << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3532kb
input:
7 4 4 3 2 S 6 3 S 6 1 1 1 2 1 3 2 3 5 1 5 3 11 2 1 3 1 3 2 5 2 6 2 2 3 4 3 5 3 6 3 3 4 6 4
output:
-1
result:
wrong answer 1st lines differ - expected: '8 1', found: '-1'