QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#98645#5612. Picking Up SteamPetroTarnavskyiWA 2ms3760kbC++174.5kb2023-04-19 15:37:172023-04-19 15:37:20

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-19 15:37:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3760kb
  • [2023-04-19 15:37:17]
  • 提交

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;
const double INF = 1e47;

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 dot(const Point& p) const {
		return x * p.x + y * p.y;
	}
	double d2() const {
		return x * x + y * y;
	}
	double len() const {
		return sqrt(d2());
	}
	Point scale(double l) const {
		return *this * (l / len());
	}
};

int sign(double x) {
	return x > EPS ? 1 : x < -EPS ? -1 : 0;
}

struct Line {
	Point n;
	double c;
	Line() {}
	Line(const Point& a, const Point& b): n(b.y - a.y, a.x - b.x), c(-n.dot(a)) {}
	double dist(const Point& p) const {
		return (n.dot(p) + c) / n.len();
	}
	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 {x, y};
	}
};

double f(const Point& s, double r, const Point& u, const Point& q) {
	if (abs(Line(s, s + u).dist(q)) > r - EPS) {
		return INF;
	}
	double a = u.d2(), b = 2 * u.dot(s - q), c = (s - q).d2() - r * r,
		D = b * b - 4 * a * c;
	double res = (-b - sqrt(D)) / (2 * a);
	return res > 0 ? res : INF;
}

bool checkPoint(const Point& c, const Point& q, const vector<Point>& p) {
	int n = SZ(p) - 1;
	if (q.x < p[0].x - EPS || q.x > p[n].x + EPS) {
		return false;
	}
	FOR(i, 0, n) {
		if (p[i].x - EPS < c.x && c.x < p[i + 1].x + EPS) {
			int j = -1;
			if (abs(c.x - p[i].x) < EPS && i > 0) {
				j = i;
			}
			if (abs(c.x - p[i + 1].x) < EPS && i < n - 1) {
				j = i + 1;
			}
			if (j == -1) {
				if (sign((p[i + 1] - p[i]) * (q - p[i])) == -1) {
					return false;
				}
				continue;
			}
			int s1 = sign((p[j] - p[j - 1]) * (q - p[j - 1])), s2 = sign((p[j + 1] - p[j]) * (q - p[j])),
				s3 = sign((p[j + 1] - p[j - 1]) * (p[j] - p[j - 1]));
			if (s3 >= 0 && s1 == -1 && s2 == -1) {
				return false;
			}
			if (s3 < 0 && (s1 == -1 || s2 == -1)) {
				return false;
			}
		}
		else {
			if (sign((p[i + 1] - p[i]) * (c - p[i])) * sign((p[i + 1] - p[i]) * (q - p[i])) != -1) {
				continue;
			}
			int s[2] = {sign((q - c) * (p[i] - c)), sign((q - c) * (p[i + 1] - c))};
			int j = p[i].y > p[i + 1].y ? 0 : 1;
			if (s[0] * s[1] <= 0 && s[j] != 0) {
				return false;
			}
		}
	}
	return true;
}

double checkLine(const Point& c, const Point& s, double r, const Point& u, const Line& l, const vector<Point>& p) {
	if (sign(l.n.dot(u)) == 0) {
		return INF;
	}
	double si = abs(l.n * u) / (l.n.len() * u.len());
	Point uPerp(-u.y, u.x);
	Point s1 = s + uPerp.scale(r * si), s2 = s - uPerp.scale(r * si);
	double res = INF;
	for (Point s0 : {s1, s2}) {
		Point q = Line(s0, s0 + u).intersect(l);
		if (checkPoint(c, q, p)) {
			res = min(res, f(s, r, u, q));
		}
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int n;
	cin >> n;
	vector<Point> p(n + 1);
	for (Point& pi : p) {
		cin >> pi.x >> pi.y;
	}
	Point c, s, u;
	double r, v;
	cin >> c.x >> s.x >> s.y >> r >> u.x >> u.y >> v;
	FOR(i, 0, n) {
		if (p[i].x - EPS < c.x && c.x < p[i + 1].x + EPS) {
			c.y = p[i].y + (c.x - p[i].x) * (p[i + 1].y - p[i].y) / (p[i + 1].x - p[i].x);
		}
	}
	u = u.scale(v);
	double ans = f(s, r, u, c);
	FOR(i, 0, n + 1) {
		if (sign(p[i].x - c.x) != 0) {
			Line l1(c, p[i]);
			ans = min(ans, checkLine(c, s, r, u, l1, p));
			FOR(j, 0, n) {
				Line l2(p[j], p[j + 1]);
				if (!l1.parallel(l2)) {
					const Point& q = l1.intersect(l2);
					if (checkPoint(c, q, p)) {
						ans = min(ans, f(s, r, u, q));
					}
				}
			}
		}
		if (i < n) {
			ans = min(ans, checkLine(c, s, r, u, Line(p[i], p[i + 1]), p));
		}
	}
	if (ans < 1e9) {
		cout << ans << "\n";
	}
	else {
		cout << "-1\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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: -100
Wrong Answer
time: 2ms
memory: 3760kb

input:

3 0 0 3 3 6 3 9 0
0 4 1 1 0 1 1

output:

4.0000000000

result:

wrong answer 1st numbers differ - expected: '1.58579', found: '4.00000', error = '1.52241'