QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100355#5612. Picking Up SteamPetroTarnavskyiWA 2ms3784kbC++174.0kb2023-04-25 17:42:102023-04-25 17:42:14

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:42:14]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3784kb
  • [2023-04-25 17:42:10]
  • 提交

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 > -EPS) {
		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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 3520kb

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

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: 1ms
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 #5:

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

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

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

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

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

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

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: 0ms
memory: 3628kb

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

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

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: 0ms
memory: 3576kb

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

input:

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

output:

-0.0000000000

result:

ok found '-0.00000', expected '0.00000', error '0.00000'

Test #16:

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

input:

20 1 11 4 1 5 14 6 8 8 8 9 1 12 14 14 12 17 8 21 6 25 1 27 8 29 4 35 5 37 16 38 17 39 16 45 9 47 4 48 11 49 2
6 21 -2 1 0 15 5

output:

4.7171572875

result:

ok found '4.71716', expected '4.71716', error '0.00000'

Test #17:

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

input:

20 2 10 4 4 6 13 9 3 10 12 11 5 12 0 14 15 15 10 17 20 19 8 21 4 28 18 29 7 32 10 36 2 39 0 40 5 41 6 42 18 47 2
33 34 -11 4 -3 13 1

output:

15.3538311384

result:

ok found '15.35383', expected '15.35383', error '0.00000'

Test #18:

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

input:

33 -4858 1505 -4750 252 -4377 2301 -4299 1512 -4124 4848 -3928 551 -3650 1782 -3242 163 -3241 4713 -2817 1286 -2753 2708 -1859 4013 -991 2481 -837 2253 356 669 385 4947 558 336 841 4286 1041 91 1122 3030 1371 4183 1456 1266 1632 844 1802 4762 2340 4087 2353 2421 2696 1915 3294 220 4405 3012 4413 481...

output:

43.6180615052

result:

ok found '43.61806', expected '43.61806', error '0.00000'

Test #19:

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

input:

20 0 11 4 18 5 0 9 5 10 17 12 2 13 0 16 11 18 3 19 5 21 3 25 19 31 2 32 6 34 13 35 9 37 20 42 0 45 12 46 14 47 4
38 9 -15 5 -1 15 3

output:

57.5750067659

result:

ok found '57.57501', expected '57.57501', error '0.00000'

Test #20:

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

input:

20 0 7 1 8 5 18 10 10 12 7 13 8 15 0 16 1 17 7 19 11 25 13 26 2 27 2 29 4 37 14 38 6 40 12 42 17 43 15 44 6 47 3
41 4 -14 1 6 5 5

output:

8.3683949411

result:

ok found '8.36839', expected '8.36839', error '0.00000'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

15 -4759 2812 -4596 3951 -4052 4157 -3244 779 -2591 4780 -1380 81 -839 3638 -757 1156 8 392 881 3169 1035 2070 1390 3818 1982 3218 2020 2830 2686 2080 3928 4241
1390 1388 -1229 398 439 4605 41

output:

100.1453774505

result:

ok found '100.14538', expected '100.14538', error '0.00000'

Test #22:

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

input:

100 2 144 10 36 12 238 14 286 17 461 19 257 20 174 25 6 32 96 38 199 52 451 59 304 61 372 64 17 65 426 70 432 76 40 77 253 79 382 82 164 84 408 94 208 99 386 102 434 103 482 104 428 111 95 112 192 114 381 117 285 124 259 130 289 131 402 133 462 136 10 138 367 147 500 150 365 153 145 156 267 157 299 ...

output:

34.4888004593

result:

ok found '34.48880', expected '34.48880', error '0.00000'

Test #23:

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

input:

100 13 43 14 384 16 276 22 343 26 375 28 453 29 369 40 265 41 153 45 81 51 446 58 58 62 388 65 187 73 109 77 167 79 59 98 316 104 257 105 133 112 68 120 345 133 95 144 290 145 70 146 375 152 118 160 362 166 75 167 479 168 48 176 141 178 45 181 339 183 355 184 261 188 221 189 267 196 108 207 263 211 ...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #24:

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

input:

100 2 193 6 307 13 193 21 160 26 80 29 116 30 136 35 398 40 228 41 161 59 180 61 120 64 310 65 285 69 268 73 261 74 79 78 30 84 135 85 85 94 485 98 195 105 143 108 50 114 129 120 30 131 247 139 223 143 147 144 431 148 1 150 452 151 443 163 461 164 25 168 210 173 339 174 41 175 224 179 211 189 112 19...

output:

92.5301107898

result:

ok found '92.53011', expected '92.53011', error '0.00000'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3784kb

input:

100 4 309 20 470 23 362 29 439 30 342 46 465 49 363 55 6 56 40 58 478 61 358 62 459 64 326 71 135 73 499 75 490 83 241 86 429 93 44 98 349 100 415 104 13 106 341 120 19 128 467 130 175 131 235 137 58 138 101 155 205 156 19 157 364 159 124 163 222 168 255 174 207 177 87 181 240 186 224 188 119 194 47...

output:

16.9862292917

result:

ok found '16.98623', expected '16.98623', error '0.00000'

Test #26:

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

input:

171 -4951 4053 -4885 4474 -4850 3308 -4820 2830 -4798 2464 -4783 4657 -4759 1857 -4599 890 -4467 1174 -4461 1849 -4352 1814 -4261 1358 -4191 4986 -4149 2579 -4004 891 -3988 4057 -3944 4843 -3886 4375 -3710 818 -3644 877 -3546 4297 -3510 4384 -3331 4080 -3286 3168 -3271 940 -3267 3829 -3206 161 -3172...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #27:

score: -100
Wrong Answer
time: 0ms
memory: 3540kb

input:

439 -4990 2843 -4970 4753 -4935 1802 -4918 2606 -4900 2888 -4886 3403 -4870 1607 -4826 3029 -4813 2183 -4742 3075 -4712 3708 -4701 1752 -4599 3587 -4583 2542 -4537 134 -4529 1165 -4515 54 -4506 2457 -4489 661 -4478 2497 -4456 503 -4443 3259 -4376 3839 -4368 745 -4353 1067 -4345 939 -4299 4447 -4274 ...

output:

2.4520164366

result:

wrong answer 1st numbers differ - expected: '1.01064', found: '2.45202', error = '1.42621'