QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#359052 | #6426. Interested in Skiing | lmf_up | AC ✓ | 6ms | 4008kb | C++20 | 8.8kb | 2024-03-20 11:32:56 | 2024-03-20 11:32:56 |
Judging History
answer
#include<bits/stdc++.h>
#define cp const point &
#define cl const line &
#define cc const circle &
#define LD long double
std::mt19937 rnd(1234567312);
const LD eps = 1e-8;
const LD pi = acosl(-1);
const LD INF = 1e9;
const int mod1 = 998244353, mod2 = 1e9 + 7;
int sgn(LD x)
{
return x > eps ? 1 : (x < -eps ? -1 : 0);
}
LD sqr(LD x)
{ return x * x; }
long long sqrll(long long x)
{
return x * x;
}
struct point
{
LD x, y;
point()
{}
point(LD xx, LD yy)
{ x = xx, y = yy; }
point operator+(cp a) const
{ return {x + a.x, y + a.y}; }
point operator-(cp a) const
{ return {x - a.x, y - a.y}; }
point operator*(LD t) const
{ return {x * t, y * t}; }
point operator/(LD t) const
{ return {x / t, y / t}; }
point rot(LD t) const
{ return {(LD) (x * cosl(t) - y * sinl(t)), (LD) (x * sinl(t) + y * cosl(t))}; }
point rot90() const
{ return {-y, x}; }
point rot270() const
{ return point(y, -x); }
LD len2() const
{ return x * x + y * y; }
LD len() const
{ return sqrtl(x * x + y * y); }
point unit() const
{
LD d = len();
return {(LD) (x / d), (LD) (y / d)};
}
int on_up()//b不判(0,0)
{
return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) < 0);
}
void print()
{
std::cout << x << ' ' << y << std::endl;
}
void read()
{
int xx, yy;
std::cin >> xx >> yy;
x = xx, y = yy;
}
friend bool operator<(cp a, cp b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
friend bool operator>(cp a, cp b)
{
return a.x == b.x ? a.y > b.y : a.x > b.x;
}
};
LD dot(cp a, cp b);
bool operator==(cp a, cp b)
{
// return !sgn(dot(a - b, a - b));
return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0; //看题目有无给出确定两实数相等的eps
}
LD dis(cp a, cp b)//两点距离
{
return sqrtl(sqr(a.x - b.x) + sqr(a.y - b.y));
}
LD dot(cp a, cp b)//点乘
{
return a.x * b.x + a.y * b.y;
}
LD det(cp a, cp b)//叉乘
{
return a.x * b.y - b.x * a.y;
}
LD deg(point a, point b)
{
a = a.unit(), b = b.unit();
LD d = dis(a, b);
return 2 * asinl(d / 2);
}
bool turn_left_strict(cp a, cp b, cp c)
{
return sgn(det(b - a, c - a)) > 0;
}
bool turn_left(cp a, cp b, cp c)
{
return sgn(det(b - a, c - a)) >= 0;
}
struct line
{
point s, t;
line()
{}
line(point a, point b) : s(a), t(b)
{}
void read()
{
s.read(), t.read();
}
void print()
{
s.print(), std::cout << ' ', t.print();
}
};
struct circle
{
point c;
LD r;
circle()
{}
circle(point C, LD R)
{ c = C, r = R; }
};
bool in_circle(cp a, cc b)
{
return sgn((b.c - a).len() - b.r) <= 0;
}
circle make_circle(point u, point v)
{
point p = (u + v) / 2;
return circle(p, (u - p).len());
}
circle make_circle(cp a, cp b, cp c)
{
point p = b - a, q = c - a;
point s(dot(p, p) / 2, dot(q, q) / 2);
LD d = det(p, q);
p = point(det(s, point(p.y, q.y)), det(point(p.x, q.x), s)) / d;
return circle(a + p, p.len());
}
circle min_circle(std::vector<point> p)
{
circle ret(p[0], 0);
std::shuffle(p.begin(), p.end(), rnd);
int len = p.size();
for (int i = 0; i < len; i++)
if (!in_circle(p[i], ret))
{
ret = circle(p[i], 0);
for (int j = 0; j < i; j++)
if (!in_circle(p[j], ret))
{
ret = make_circle(p[j], p[i]);
for (int k = 0; k < j; ++k)
if (!in_circle(p[k], ret))
ret = make_circle(p[i], p[j], p[k]);
}
}
return ret;
}
LD get_rad(point a, point b)
{
if (a == point(0, 0) || b == point(0, 0))
return 0;
else
{
return acosl(dot(a, b) / (a.len() * b.len()));
}
}
bool same_dir(cl a, cl b)//判断方向是否一致
{
return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}
bool point_on_line(cp a, cl l)//判断点是否在直线上
{
return sgn(det(a - l.s, l.t - l.s)) == 0;
}
bool point_on_segment(cp a, cl l)//判断点是否在线段上
{
return point_on_line(a, l) && sgn(dot(l.s - a, l.t - a)) < 0;//(<=代表可以端点
}
bool two_side(cp a, cp b, cl c)//判断两个点是否在线段的两边
{
return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}
bool intersect_judge_strict(cl a, cl b)
{
return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}
bool intersect_judge(cl a, cl b)
{//判断两个线段是否相交
if (point_on_segment(a.s, b) || point_on_segment(a.t, b) || point_on_segment(b.s, a) ||
point_on_segment(b.t, a))
return true;
return intersect_judge_strict(a, b);
}
point line_intersect(cl a, cl b)
{//得到两线段的交点
LD s1 = det(a.t - a.s, b.s - a.s);
LD s2 = det(a.t - a.s, b.t - a.s);
return (b.s * s2 - b.t * s1) / (s2 - s1);
}
LD point_to_segment(cp a, cl b)
{//点到线段的距离
if (b.s == b.t)
return dis(a, b.s);
if (sgn(dot(b.s - a, b.t - b.s)) * sgn(dot(b.t - a, b.t - b.s)) <= 0)
return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
return std::min(dis(a, b.s), dis(a, b.t));
}
std::vector<point> circle_intersect(cc a, cc b)//求两个圆的交
{
if (a.c == b.c || sgn(dis(a.c, b.c) - a.r - b.r) > 0 || sgn(dis(a.c, b.c) - abs(a.r - b.r)) < 0)
return {};
point r = (b.c - a.c).unit();
LD d = dis(a.c, b.c);
LD x = ((sqr(a.r) - sqr(b.r)) / d + d) / 2;
LD h = sqrtl(sqr(a.r) - sqr(x));
if (sgn(h) == 0)return {a.c + r * x};
return {a.c + r * x + r.rot90() * h, a.c + r * x - r.rot90() * h};
}
std::vector<point> tangent(cp a, cc b)//求一个点关于圆的切线
{
circle p = make_circle(a, b.c);
return circle_intersect(p, b);
}
std::vector<point> convex_hull(std::vector<point> a)
{//凸包,字典序
int n = (int) a.size(), cnt = 0;
if (n < 2) return a;
std::sort(a.begin(), a.end()); // less<pair>
std::vector<point> ret;
for (int i = 0; i < n; ++i)
{
while (cnt > 1
&& !turn_left_strict(ret[cnt - 1], a[i], ret[cnt - 2]))
--cnt, ret.pop_back();
++cnt, ret.push_back(a[i]);
}
int fixed = cnt;
for (int i = n - 2; i >= 0; --i)
{
while (cnt > fixed
&& !turn_left_strict(ret[cnt - 1], a[i], ret[cnt - 2]))
--cnt, ret.pop_back();
++cnt, ret.push_back(a[i]);
}
ret.pop_back();
return ret;
}
void solve()
{
int n, m, vy;
std::cin >> n >> m >> vy;
std::vector<point> pu;
std::vector<line> li(n);
for (int i = 0; i < n; i++)
{
point p1, p2;
p1.read(), p2.read();
pu.push_back(p1);
pu.push_back(p2);
li[i] = line(p1, p2);
}
std::sort(pu.begin(), pu.end(), [&](auto u, auto v)
{ return u.y < v.y; });
int len_pu = pu.size();
std::vector<LD> dp(len_pu, 1e18);
std::function<bool(line)> check = [&](line a)
{
for (int i = 0; i < n; i++)
{
if (intersect_judge_strict(a, li[i]))
return false;
}
return true;
};
LD ans = 1e18;
for (int i = 0; i < len_pu; i++)
{
auto [x, y] = pu[i];
if (sgn(x - m) == 0 || sgn(x + m) == 0)
continue;
if (check(line(point(x, -11111), pu[i])))
{
dp[i] = 0;
if (check(line(point(x, 11111), pu[i])))
{
std::cout << 0 << std::endl;
return;
}
}
for (int j = 0; j < i; j++)
{
if (sgn(pu[j].y - pu[i].y) == 0)
break;
if (check(line(pu[i], pu[j])))
dp[i] = std::min(dp[i], std::max(dp[j], std::abs(pu[j].x - pu[i].x) / ((pu[i].y - pu[j].y)) ));
}
if (check(line(point(x, 11111), pu[i])))
ans = std::min(ans, dp[i]);
}
if (check(line(point(0, -11111), point(0, 11111))))
{
std::cout<<0<<std::endl;
return ;
}
if (ans > 1e9)
{
std::cout << -1 << std::endl;
return;
}
std::cout << ans*vy << std::endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
std::cout << std::fixed << std::setprecision(10);
int T = 1;
for (int i = 1; i <= T; i++)
solve();
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4008kb
input:
3 2 1 -2 0 1 0 -1 4 2 4 0 1 0 3
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 1 2 -1 0 1 0 1 1 0 1
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
2 3 7 -3 0 2 2 3 1 -2 17
output:
1.8666666667
result:
ok found '1.8666667', expected '1.8666667', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1 100 1 -100 0 99 0
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
3 8 3 -8 -9 0 -9 -6 -6 6 6 8 9 0 9
output:
6.0000000000
result:
ok found '6.0000000', expected '6.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
3 8 3 -8 9 0 9 -6 6 6 -6 8 -9 0 -9
output:
6.0000000000
result:
ok found '6.0000000', expected '6.0000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 1 2 -1 0 0 0 1 1 0 1
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
3 9 10 -9 -26 0 -8 -6 -6 6 6 9 26 0 8
output:
30.0000000000
result:
ok found '30.0000000', expected '30.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 9 10 -9 26 0 8 -6 6 6 -6 9 -26 0 -8
output:
30.0000000000
result:
ok found '30.0000000', expected '30.0000000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
4 9 5 -9 -4 -3 0 -6 2 6 2 -6 -6 2 -8 -4 -12 9 -25
output:
7.5000000000
result:
ok found '7.5000000', expected '7.5000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 3ms
memory: 3924kb
input:
100 10000 2 1663 -5179 1091 -542 -5687 -1048 7838 4346 3959 -2780 1099 -9402 -8661 -856 3945 7651 -1688 5290 -3518 2625 10000 -8028 5857 -9678 -9929 4601 -6350 3819 -1173 -9608 -2422 -9939 10000 -4668 5423 -2597 -572 -9335 -5787 -7658 -10000 1589 3117 9331 9818 4874 1345 1669 9026 -8243 2952 -6411 8...
output:
5.9776075427
result:
ok found '5.9776075', expected '5.9776075', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
20 100 5 100 55 77 -18 60 -33 45 -1 41 41 -84 53 66 -77 30 -70 44 -15 -45 -98 -36 19 67 29 51 -71 89 -50 100 -48 92 -39 43 20 -22 -33 10 -71 7 -52 -100 -9 -4 13 -100 90 -19 81 73 67 6 54 -86 2 -91 67 59 -35 77 -55 -43 -40 -58 -41 100 82 -39 55 40 -17 39 -12 42 4 84 -52 61 78 -46 86
output:
27.0000000000
result:
ok found '27.0000000', expected '27.0000000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
20 100 1 90 -37 -90 90 -61 46 -83 42 26 -45 -89 -79 -100 -3 -51 -34 40 -57 22 -70 90 55 17 75 5 -50 -35 24 -1 -20 33 -19 -69 78 100 -13 -45 -52 -89 -15 100 -100 -3 -23 49 84 78 95 -48 43 -21 -23 100 53 78 84 65 -42 84 -61 100 23 100 19 -58 38 -48 18 26 -53 -51 -92 29 37 -81 90 -5 82 43 30
output:
1.3181818182
result:
ok found '1.3181818', expected '1.3181818', error '0.0000000'
Test #14:
score: 0
Accepted
time: 3ms
memory: 3876kb
input:
100 10000 9 9893 -5 -4023 94 2920 -32 -2174 -97 7462 24 4169 40 -6157 -25 -6492 40 5908 -16 647 48 4128 -19 -5163 -5 4082 96 7645 37 -8896 29 -2485 59 165 1 -1634 59 7644 -64 6345 -96 -8569 46 -5850 72 -2219 -64 -5429 -13 641 -36 -3923 -25 -1947 6 -3957 43 8241 -6 -2456 77 5268 -95 890 -75 3296 78 -...
output:
3037.1538461538
result:
ok found '3037.1538462', expected '3037.1538462', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
10 50 4 5 -45 22 -48 -50 20 -23 19 -43 -29 35 31 50 -33 40 48 -49 -32 0 -33 16 -50 21 -49 50 -38 -22 -18 -49 50 11 14 20 -23 16 -11 -27 -15 35 32
output:
3.3548387097
result:
ok found '3.3548387', expected '3.3548387', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
10 50 1 -50 -3 28 -3 7 -30 2 -30 34 39 50 39 16 22 43 22 50 -32 7 -32 50 15 -2 15 -15 -42 24 -42 14 -26 28 -26 23 -10 -39 -10 50 -44 -31 -44
output:
1.6666666667
result:
ok found '1.6666667', expected '1.6666667', error '0.0000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
10 50 2 35 10 7 22 -47 -23 -34 8 44 27 14 47 50 -13 -43 -48 44 -15 20 -12 -42 -34 11 -5 50 -5 -32 19 17 -39 46 -27 50 -2 11 20 -1 29 30 31
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #18:
score: 0
Accepted
time: 6ms
memory: 3860kb
input:
100 10000 10 0 9993 -10000 9997 -8432 1663 -4444 1091 -6362 3959 -103 1099 -6051 -8548 -5705 -3821 -1799 4343 -9251 8281 -10000 -1137 -6247 718 -10000 -1352 -641 -1609 -2741 -1688 -2924 -3518 -10000 5035 -7198 5857 -4181 -9929 -3009 -6350 -9568 -9578 -7653 -9810 -9208 2799 -8703 3189 -10000 -3228 -3...
output:
0.0015005252
result:
ok found '0.0015005', expected '0.0015005', error '0.0000000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
7 70 6 -63 -598 7 -598 70 260 14 104 35 26 -21 -182 -21 -286 -21 -494 -56 -208 -56 -572 -70 0 0 0 -42 -208 -14 -208
output:
1.6153846154
result:
ok found '1.6153846', expected '1.6153846', error '0.0000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
1 10 1 -10 0 -10 10
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2 3 1 2 0 2 3 -3 1 2 100
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 3 1 -3 -3 2 -1 0 -1 0 2 -2 2 3 5
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 3 1 -3 -3 2 -1 0 0 0 2 -2 2 3 5
output:
2.0000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5 3 1 -3 -3 0 0 0 -4 3 -4 0 1 0 2 0 -1 0 -2 0 -9 0 -1000
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'