QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100348 | #5612. Picking Up Steam | PetroTarnavskyi | RE | 3ms | 3736kb | C++17 | 4.4kb | 2023-04-25 17:32:17 | 2023-04-25 17:32:18 |
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;
#define double long double
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) {
double a = u.d2(), b = 2 * u.dot(s - q), c = (s - q).d2() - r * r,
D = b * b - 4 * a * c;
if (D < 0 || sqrt(D) / a < EPS) {
return INF;
}
double res = (-b - sqrt(max((double)0.0, D))) / (2 * a);
return res > -EPS ? 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 + 1) {
if (i < n && p[i].x - EPS < q.x && q.x < p[i + 1].x + EPS && sign((p[i + 1] - p[i]) * (q - p[i]) / (p[i + 1] - p[i]).len() / (q - p[i]).len()) == -1) {
return false;
}
if (sign(p[i].x - c.x) * sign(p[i].x - q.x) == -1 && sign((p[i] - c) * (q - c) / (p[i] - c).len() / (q - c).len()) * sign(p[i].x - c.x) == -1) {
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) / l.n.len() / u.len()) == 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);
Line lLeft(p[0], {p[0].x, p[0].y + 1}), lRight(p[n], {p[n].x, p[n].y + 1});
ans = min(ans, checkLine(c, s, r, u, lLeft, p));
ans = min(ans, checkLine(c, s, r, u, lRight, p));
FOR(i, 0, n + 1) {
if (checkPoint(c, p[i], p)) {
ans = min(ans, f(s, r, u, p[i]));
}
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, -1, n + 1) {
Line l2;
if (j == -1) {
l2 = lLeft;
}
else if (j == n) {
l2 = lRight;
}
else {
l2 = Line(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));
}
}
assert(ans > 1e-3);
if (ans < 1e9) {
cout << ans << "\n";
}
else {
cout << "-1\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
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: 3ms
memory: 3516kb
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: 3620kb
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: 3512kb
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: 3624kb
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: 3588kb
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: 3532kb
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: 3736kb
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: 3524kb
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: 1ms
memory: 3628kb
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: 3736kb
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: 1ms
memory: 3720kb
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: 2ms
memory: 3512kb
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: 3524kb
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
Dangerous Syscalls
input:
2 0 3 3 0 6 3 1 3 -1 1 0 1 1