QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100353#5612. Picking Up SteamPetroTarnavskyiWA 2ms3792kbC++174.0kb2023-04-25 17:40:022023-04-25 17:40:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 17:40:06]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3792kb
  • [2023-04-25 17:40:02]
  • 提交

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;

#define double long double

const double EPS = 1e-6;

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;
	}
	double dot(const Point& p) const {
		return x * p.x + y * p.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 + 1) {
		if (p[i].x > l + EPS && p[i].x < r - EPS && (p2 - p1) * (p[i] - p1) > EPS) {
			return i;
		}
	}
	return -1;
}

Point c, s;
double r, dx, dy, v;
Point direction;

double f(const Point& q) {
	double a = v * v;
	double b = 2 * (s - q).dot(direction);
	double cc = (s - q).d2() - r * r;
	double D = b * b - 4 * a * cc;
	if (D < EPS) {
		return 1e18;
	}
	double cur = (-b - sqrt(D)) / (2 * a);
	if (cur > 0) {
		return cur;
	}
	return 1e18;
}

vector<Point> intersectLine(const Point& p1, const Point& p2, const Line& traj) {
	Line l(p1, p2);
	Point q = traj.intersect(l);
	double si = abs(traj.n * l.n) / traj.n.len() / l.n.len();
	double alpha = asin(si);
	Point dq = (p2 - p1).scale(r * cos(alpha) / si);
	return {q - dq, q + dq};
}

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;
	direction = Point(dx, dy).scale(v);
	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, s + direction);
		if (direction * (c - s) > 0) {
			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;
				}
				for (const auto& pt : intersectLine(c, p[i], traj)) {
					if ((j == -1 || pt.x < q.x + EPS) && pt.x > c.x - EPS && pt.x < p[n].x + EPS) {
						t = min(t, f(pt));
					}
				}
			}
		}
		FOR(i, 0, n) {
			Line l(p[i], p[i + 1]);
			if (traj.parallel(l)) {
				continue;
			}
			for (auto pt : intersectLine(p[i], p[i + 1], traj)) {
				if (pt.x > p[i].x - EPS && pt.x < p[i + 1].x + EPS && pt.x > c.x - EPS && findPointAbove(c, pt, c.x, pt.x) == -1) {
					t = min(t, f(pt));
				}
			}
		}
		for (Point& pi : p) {
			pi.x *= -1;
		}
		c.x *= -1;
		s.x *= -1;
		direction.x *= -1;
		reverse(ALL(p));
	}
	if (t > 1e17) {
		cout << "-1\n";
	}
	else {
		cout << t << "\n";
	}
	return 0;
}


详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3632kb

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: 3624kb

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: 3520kb

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: 3776kb

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: 2ms
memory: 3792kb

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: 3628kb

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: 3456kb

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: 1ms
memory: 3776kb

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: 0
Accepted
time: 2ms
memory: 3596kb

input:

5 0 80 40 0 60 60 100 0 120 40 160 60
0 140 20 20 -1 1 1

output:

7.2024201797

result:

ok found '7.20242', expected '7.20242', error '0.00000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

5 0 80 40 0 60 60 100 0 120 40 160 60
0 140 20 20 0 1 1

output:

7.6393202250

result:

ok found '7.63932', expected '7.63932', error '0.00000'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

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

output:

2.0065727096

result:

ok found '2.00657', expected '2.00657', error '0.00000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3520kb

input:

9 -12 5 -10 2 -8 7 -6 5 -5 2 -3 2 -2 3 -1 6 1 6 3 4
0 -8 3 1 1 1 1

output:

2.8284271247

result:

ok found '2.82843', expected '2.82843', error '0.00000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

9 -12 5 -10 2 -8 7 -6 5 -5 2 -3 2 -2 3 -1 6 1 6 3 4
-12 -8 3 1 1 1 1

output:

8.1514308388

result:

ok found '8.15143', expected '8.15143', error '0.00000'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3528kb

input:

8 -4956 0 -413 0 413 1239 1239 0 1652 826 2478 826 3404 1239 3717 1239 5000 0
413 -1239 -1652 413 2 1 1

output:

2770.4882241222

result:

ok found '2770.48822', expected '2770.48822', error '0.00000'

Test #15:

score: -100
Wrong Answer
time: 1ms
memory: 3712kb

input:

2 0 3 3 0 6 3
1 3 -1 1 0 1 1

output:

1.0000000000

result:

wrong answer 1st numbers differ - expected: '0.00000', found: '1.00000', error = '1.00000'