QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94774#5605. A-Mazing PuzzlePetroTarnavskyi#WA 2ms3532kbC++173.1kb2023-04-07 18:14:552023-04-07 18:14:56

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-07 18:14:56]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3532kb
  • [2023-04-07 18:14:55]
  • 提交

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'