QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94790 | #5612. Picking Up Steam | PetroTarnavskyi# | WA | 2ms | 4152kb | C++17 | 4.0kb | 2023-04-07 19:21:17 | 2023-04-07 19:21:19 |
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};
}
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;
}
Point operator*(double k) const {
return {k * x, k * y};
}
double d2() const {
return x * x + y * y;
}
double len() const {
return sqrt(d2());
}
Point scale(double l) const {
return (*this) * (l / len());
}
};
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;
}
Point c, s;
double r, dx, dy, v;
double f(const Point& q) {
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) {
return 1e18;
}
double cur = (-b - sqrt(D)) / (2 * a);
if (cur > 0) {
return cur;
}
return 1e18;
}
pair<Point, double> intersectLine(const Point& p1, const Point& p2, const Line& traj) {
Line l(p1, p2);
Point q = traj.intersect(l);
double dist = (s - q).len();
double si = abs(traj.n * l.n) / traj.n.len() / l.n.len();
double alpha = asin(si);
q = q - (p2 - p1).scale(r * cos(alpha) / si);
return {q, (dist - r / si) / v};
}
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;
}
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 = f(c);
FOR(it, 0, 2) {
Line traj(s, Point(s.x + dx, s.y + dy));
FOR(i, 0, n + 1) {
if (p[i].x < c.x + EPS || findPointAbove(c, p[i], c.x, p[i].x) != -1) {
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]));
t = min(t, f(q));
}
if (traj.parallel(l)) {
continue;
}
auto pt = intersectLine(c, p[i], traj);
if ((j == -1 || pt.first.x < q.x) && pt.first.x >= p[0].x && pt.first.x <= p[n].x) {
t = min(t, pt.second);
}
}
FOR(i, 0, n) {
Line l(p[i], p[i + 1]);
if (traj.parallel(l)) {
continue;
}
auto pt = intersectLine(p[i], p[i + 1], traj);
if (pt.first.x > p[i].x - EPS && pt.first.x < p[i + 1].x + EPS && pt.first.x > c.x - EPS && findPointAbove(c, pt.first, c.x, pt.first.x) == -1) {
if (pt.first.x >= p[0].x && pt.first.x <= p[n].x) {
t = min(t, pt.second);
}
}
}
for (Point& pi : p) {
pi.x *= -1;
}
c.x *= -1;
s.x *= -1;
dx *= -1;
reverse(ALL(p));
}
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: 100
Accepted
time: 2ms
memory: 4032kb
input:
7 1 0 2 2 4 2 5 5 6 0 9 4 12 3 14 0 2 13 -1 1 -1 1 1
output:
8.8994949366
result:
ok found '8.89949', expected '8.89900', error '0.00006'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3988kb
input:
3 0 0 3 3 6 3 9 0 3 4 1 1 -1 1 1
output:
1.1213203436
result:
ok found '1.12132', expected '1.12132', error '0.00000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3876kb
input:
3 0 0 3 3 6 3 9 0 4 4 1 1 -1 1 1
output:
1.4142135624
result:
ok found '1.41421', expected '1.41421', error '0.00000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
3 0 0 3 3 6 3 9 0 4 4 1 1 1 1 1
output:
1.4142135624
result:
ok found '1.41421', expected '1.41421', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
3 0 0 3 3 6 3 9 0 8 4 1 1 1 1 1
output:
1.8284271247
result:
ok found '1.82843', expected '1.82843', error '0.00000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3992kb
input:
3 0 0 3 3 6 3 9 0 0 4 1 1 0 1 1
output:
1.5857864376
result:
ok found '1.58579', expected '1.58579', error '0.00000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 4152kb
input:
3 0 0 3 3 6 3 9 0 0 4 1 1 1 1 1
output:
-1
result:
ok found '-1.00000', expected '-1.00000', error '-0.00000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 4068kb
input:
2 10 10 30 40 60 60 50 40 30 10 -1 1 1
output:
3.9440965965
result:
ok found '3.94410', expected '3.94410', error '0.00000'
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 3992kb
input:
5 0 80 40 0 60 60 100 0 120 40 160 60 0 140 20 20 -1 1 1
output:
-16.4370883025
result:
wrong answer 1st numbers differ - expected: '7.20242', found: '-16.43709', error = '3.28216'