QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#78522 | #5505. Great Chase | yuto1115 | AC ✓ | 1297ms | 9576kb | C++17 | 17.9kb | 2023-02-19 11:33:48 | 2023-02-19 11:33:50 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d)
#define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--)
#define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--)
#define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d)
#define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SORT(a) sort(all(a));
#define REV(a) reverse(all(a));
#define SZ(a) int(a.size())
#define popcount(x) __builtin_popcountll(x)
#define pf push_front
#define pb push_back
#define ef emplace_front
#define eb emplace_back
#define ppf pop_front
#define ppb pop_back
#ifdef __LOCAL
#define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; }
#else
#define debug(...) void(0);
#endif
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vp = vector<P>;
using vvp = vector<vp>;
using vlp = vector<LP>;
using vvlp = vector<vlp>;
template<class T>
using PQ = priority_queue<T>;
template<class T>
using PQrev = priority_queue <T, vector<T>, greater<T>>;
template<class S, class T>
istream &operator>>(istream & is, pair < S, T > &p) { return is >> p.first >> p.second; }
template<class S, class T>
ostream &operator<<(ostream &os, const pair <S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; }
template<class S, class T, class U>
istream &operator>>(istream & is, tuple < S, T, U > &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); }
template<class S, class T, class U>
ostream &operator<<(ostream &os, const tuple<S, T, U> &t) {
return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}';
}
template<class T>
istream &operator>>(istream & is, vector < T > &v) {
for (T &t: v) { is >> t; }
return is;
}
template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
os << '[';
rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
return os << ']';
}
template<class T>
ostream &operator<<(ostream &os, const deque <T> &v) {
os << '[';
rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
return os << ']';
}
template<class T>
ostream &operator<<(ostream &os, const set <T> &st) {
os << '{';
auto it = st.begin();
while (it != st.end()) {
os << (it == st.begin() ? "" : ", ") << *it;
it++;
}
return os << '}';
}
template<class T>
ostream &operator<<(ostream &os, const multiset <T> &st) {
os << '{';
auto it = st.begin();
while (it != st.end()) {
os << (it == st.begin() ? "" : ", ") << *it;
it++;
}
return os << '}';
}
template<class T, class U>
ostream &operator<<(ostream &os, const map <T, U> &mp) {
os << '{';
auto it = mp.begin();
while (it != mp.end()) {
os << (it == mp.begin() ? "" : ", ") << *it;
it++;
}
return os << '}';
}
template<class T>
void vecout(const vector <T> &v, char div = '\n') {
rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div);
}
template<class T>
bool constexpr chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool constexpr chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
void scan() {}
template<class Head, class... Tail>
void scan(Head &head, Tail &... tail) {
cin >> head;
scan(tail...);
}
template<class T>
void print(const T &t) { cout << t << '\n'; }
template<class Head, class... Tail>
void print(const Head &head, const Tail &... tail) {
cout << head << ' ';
print(tail...);
}
template<class T>
vector <T> &operator+=(vector <T> &v, T x) {
for (T &t: v) t += x;
return v;
}
template<class T>
vector <T> &operator-=(vector <T> &v, T x) {
for (T &t: v) t -= x;
return v;
}
template<class T>
vector <T> &operator*=(vector <T> &v, T x) {
for (T &t: v) t *= x;
return v;
}
template<class T>
vector <T> &operator/=(vector <T> &v, T x) {
for (T &t: v) t /= x;
return v;
}
struct Init_io {
Init_io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << boolalpha << fixed << setprecision(15);
cerr << boolalpha << fixed << setprecision(15);
}
} init_io;
const string yes[] = {"no", "yes"};
const string Yes[] = {"No", "Yes"};
const string YES[] = {"NO", "YES"};
const int inf = 1001001001;
const ll linf = 1001001001001001001;
void rearrange(const vi &) {}
template<class T, class... Tail>
void rearrange(const vi &ord, vector <T> &head, Tail &...tail) {
assert(ord.size() == head.size());
vector <T> ori = head;
rep(i, ord.size()) head[i] = ori[ord[i]];
rearrange(ord, tail...);
}
template<class T, class... Tail>
void sort_by(vector <T> &head, Tail &... tail) {
vi ord(head.size());
iota(all(ord), 0);
sort(all(ord), [&](int i, int j) { return head[i] < head[j]; });
rearrange(ord, head, tail...);
}
bool in_rect(int i, int j, int h, int w) {
return 0 <= i and i < h and 0 <= j and j < w;
}
template<class T>
constexpr vector <T> pow_table(int n, T base) {
vector <T> res(n, 1);
rep(i, n - 1) res[i + 1] = res[i] * base;
return res;
}
template<class T, class S>
vector <T> cumsum(const vector <S> &v, bool shift_one = true) {
int n = v.size();
vector <T> res;
if (shift_one) {
res.resize(n + 1);
rep(i, n) res[i + 1] = res[i] + v[i];
} else {
res.resize(n);
if (n) {
res[0] = v[0];
rep(i, 1, n) res[i] = res[i - 1] + v[i];
}
}
return res;
}
vvi graph(int n, int m, bool directed = false, int origin = 1) {
vvi G(n);
rep(_, m) {
INT(u, v);
u -= origin, v -= origin;
G[u].pb(v);
if (!directed) G[v].pb(u);
}
return G;
}
template<class T>
vector <vector<pair < int, T>>>
weighted_graph(int n, int m, bool directed = false, int origin = 1) {
vector < vector < pair < int, T>>> G(n);
rep(_, m) {
int u, v;
T w;
scan(u, v, w);
u -= origin, v -= origin;
G[u].eb(v, w);
if (!directed) G[v].eb(u, w);
}
return G;
}
const double eps = 1e-9;
const double PI = acos(-1);
int sgn(double a) { return a < -eps ? -1 : (a > eps ? 1 : 0); }
double to_rad(double deg) { return deg * PI / 180; }
double to_deg(double rad) { return rad * 180 / PI; }
struct point {
double x, y;
point(double x = 0, double y = 0) : 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}; }
point operator*(double a) const { return {x * a, y * a}; }
point operator*(const point &p) const { return point(x * p.x - y * p.y, x * p.y + y * p.x); }
point operator/(double a) const { return {x / a, y / a}; }
point operator-() const { return *this * (-1); }
bool operator==(const point &p) const { return !sgn(x - p.x) && !sgn(y - p.y); }
bool operator!=(const point &p) const { return !(*this == p); }
bool operator<(const point &p) const { return sgn(x - p.x) ? x < p.x : y < p.y; }
bool operator>(const point &p) const { return sgn(x - p.x) ? x > p.x : y > p.y; }
double norm() const { return x * x + y * y; }
double abs() const { return sqrt(norm()); }
point rot(double rad) const { return point(cos(rad) * x - sin(rad) * y, sin(rad) * x + cos(rad) * y); }
point rot90() const { return point(-y, x); }
double arg() const {
double res = atan2(y, x);
if (sgn(res) < 0) res += 2 * PI;
return res;
}
};
istream &operator>>(istream & is, point & p) { return is >> p.x >> p.y; }
ostream &operator<<(ostream &os, const point &p) { return os << '(' << p.x << "," << p.y << ')'; }
double dist(const point &a, const point &b) { return (a - b).abs(); }
double dot(const point &a, const point &b) { return a.x * b.x + a.y * b.y; }
double cross(const point &a, const point &b) { return a.x * b.y - a.y * b.x; }
point mid(const point &a, const point &b) { return (a + b) / 2; }
int ccw(const point &a, const point &b, const point &c) {
// 1 -> c is upper than line(a,b)
// -1 -> c is lower than line(a,b)
// 2 -> in order [a,b,c]
// -2 -> in order [c,a,b]
// 0 -> in order [a,c,b]
point nb = b - a, nc = c - a;
if (sgn(cross(nb, nc))) return sgn(cross(nb, nc));
if (sgn(dot(nb, nc)) < 0) return -2;
if (sgn(nc.abs() - nb.abs()) > 0) return 2;
return 0;
}
struct line {
point a, b;
line(point a = point(), point b = point()) : a(a), b(b) {}
bool online(const point &p) const { return abs(ccw(a, b, p)) != 1; }
};
ostream &operator<<(ostream &os, const line &l) { return os << '{' << l.a << ',' << l.b << '}'; }
struct segment {
point a, b;
segment(point a = point(), point b = point()) : a(a), b(b) {}
bool online(const point &p) const { return !ccw(a, b, p); }
line vertical_bisector() const { return line(mid(a, b), mid(a, b) + (b - a).rot90()); }
};
ostream &operator<<(ostream &os, const segment &l) { return os << '{' << l.a << ',' << l.b << '}'; }
bool vertical(const line &l, const line &m) { return !sgn(dot(l.a - l.b, m.a - m.b)); }
bool vertical(const segment &l, const segment &m) { return !sgn(dot(l.a - l.b, m.a - m.b)); }
bool parallel(const line &l, const line &m) { return !sgn(cross(l.a - l.b, m.a - m.b)); }
bool parallel(const segment &l, const segment &m) { return !sgn(cross(l.a - l.b, m.a - m.b)); }
bool operator==(const line &l, const line &m) { return parallel(l, m) && l.online(m.a); }
bool operator!=(const line &l, const line &m) { return !(l == m); }
bool operator==(const segment &l, const segment &m) { return l.a == m.a && l.b == m.b || l.a == m.b && l.b == m.a; }
bool operator!=(const segment &l, const segment &m) { return !(l == m); }
// intersect at one point
bool intersect(const line &l, const line &m) { return !parallel(l, m); }
bool intersect(const line &l, const segment &m) {
return sgn(cross(l.b - l.a, m.a - l.a) * cross(l.b - l.a, m.b - l.a)) <= 0;
}
bool intersect(const segment &l, const segment &m) {
return ccw(l.a, l.b, m.a) * ccw(l.a, l.b, m.b) <= 0 &&
ccw(m.a, m.b, l.a) * ccw(m.a, m.b, l.b) <= 0;
}
point intersection(const line &l, const line &m) {
assert(intersect(l, m));
return l.a + (l.b - l.a) * cross(m.b - m.a, m.a - l.a) / cross(m.b - m.a, l.b - l.a);
}
point intersection(const line &l, const segment &m) {
assert(intersect(l, m));
return l.a + (l.b - l.a) * cross(m.b - m.a, m.a - l.a) / cross(m.b - m.a, l.b - l.a);
}
point intersection(const segment &l, const segment &m) {
assert(intersect(l, m));
return l.a + (l.b - l.a) * cross(m.b - m.a, m.a - l.a) / cross(m.b - m.a, l.b - l.a);
}
double dist(const line &l, const point &p) { return abs(cross(l.b - l.a, p - l.a)) / (l.b - l.a).abs(); }
double dist(const segment &l, const point &p) {
if (sgn(dot(l.b - l.a, p - l.a)) < 0) return dist(p, l.a);
if (sgn(dot(l.a - l.b, p - l.b)) < 0) return dist(p, l.b);
return dist(line(l.a, l.b), p);
}
double dist(const line &l, const line &m) {
if (parallel(l, m)) return dist(l, m.a);
return 0;
}
double dist(const line &l, const segment &m) {
if (intersect(l, m)) return 0;
return min(dist(l, m.a), dist(l, m.b));
}
double dist(const segment &l, const segment &m) {
if (intersect(l, m)) return 0;
return min({dist(l, m.a), dist(l, m.b), dist(m, l.a), dist(m, l.b)});
}
point projection(const line &l, const point &p) {
double d = dot(p - l.a, l.b - l.a) / (l.b - l.a).norm();
return l.a + (l.b - l.a) * d;
}
point circumcenter(const point &a, const point &b, const point &c) {
return intersection(segment(a, b).vertical_bisector(), segment(b, c).vertical_bisector());
}
struct circle {
point o;
double r;
circle(point o = point(), double r = 0) : o(o), r(r) {}
bool inside(const point &p) const { return sgn(r - dist(o, p)) >= 0; }
double area() const { return r * r * PI; }
};
ostream &operator<<(ostream &os, const circle &c) { return os << '{' << c.o << ',' << c.r << '}'; }
bool intersect(const circle &c, const line &l) { return sgn(dist(l, c.o) - c.r) <= 0; }
bool intersect(const circle &c, const segment &l) {
if (sgn(dist(l, c.o) - c.r) > 0) return false;
return sgn(max((c.o - l.a).abs(), (c.o - l.b).abs()) - c.r) >= 0;
}
vector <point> intersection(const circle &c, const line &l) {
point p = projection(l, c.o);
if (!intersect(c, l)) return {};
if (sgn(dist(l, c.o) - c.r) == 0) return {p};
point e = (l.b - l.a) / (l.b - l.a).abs();
double d = sqrt(c.r * c.r - (p - c.o).norm());
return {p - e * d, p + e * d};
}
vector <point> intersection(const circle &c, const segment &l) {
auto v = intersection(c, line(l.a, l.b));
vector <point> ret;
for (point p: v) if (l.online(p)) ret.pb(p);
return ret;
}
vector <point> intersection(const circle &a, const circle &b) {
double d = dist(a.o, b.o);
if (!sgn(a.r + b.r - d)) return {a.o + (b.o - a.o) * a.r / d};
if (!sgn(a.r - b.r - d)) return {a.o + (b.o - a.o) * a.r / d};
if (!sgn(b.r - a.r - d)) return {b.o + (a.o - b.o) * b.r / d};
if (sgn(abs(a.r - b.r) - d) > 0 || sgn(a.r + b.r - d) < 0) return {};
double x = (a.r * a.r + d * d - b.r * b.r) / (2 * d);
double y = sqrt(a.r * a.r - x * x);
point p = (b.o - a.o).rot90() * y / d;
point to_mid = a.o + (b.o - a.o) * x / d;
return {to_mid - p, to_mid + p};
}
vector <circle> circle_with_two_points_and_radius(const point &a, const point &b, const double &r) {
if (sgn(dist(a, b) - 2 * r) > 0) return {};
circle A(a, r), B(b, r);
auto v = intersection(A, B);
vector <circle> ret;
for (point p: v) ret.eb(p, r);
return ret;
};
vector <point> tangent_point(const circle &c, const point &p) {
int s = sgn(dist(c.o, p) - c.r);
if (s < 0) return {};
if (s == 0) return {p};
double d = (p - c.o).norm() - c.r * c.r;
return intersection(c, circle(p, sqrt(d)));
}
vector <line> tangent_line(const circle &c, const point &p) {
vector <point> v = tangent_point(c, p);
if (v.empty()) return {};
if (v.size() == 1) return {line(p, p + (c.o - p).rot90())};
vector <line> res;
for (auto tp: v) res.eb(p, tp);
return res;
}
vector <line> tangent_line(const circle &a, const circle &b) {
if (sgn(a.r - b.r) < 0) return tangent_line(b, a);
double ar = a.r, br = b.r, d = dist(a.o, b.o);
if (sgn(d - (ar - br)) < 0) return {};
else if (sgn(d - (ar - br)) == 0) {
point p = (a.o * (-br) + b.o * ar) / (ar - br);
return {line(p, p + (a.o - p).rot90())};
} else {
vector <line> res;
{
double theta = acos((ar - br) / d);
{
point p = a.o + ((b.o - a.o) / d * ar).rot(-theta);
res.eb(p, p + (a.o - p).rot90());
}
{
point p = a.o + ((b.o - a.o) / d * ar).rot(theta);
res.eb(p, p + (a.o - p).rot90());
}
}
if (sgn(d - (ar + br)) >= 0) {
point p = (a.o * br + b.o * ar) / (ar + br);
vector <line> lines = tangent_line(a, p);
for (line l: lines) res.pb(l);
}
return res;
}
}
vector <point> convex_hull(vector <point> v) {
sort(all(v));
int n = v.size(), k = 0;
vector <point> res(2 * n);
for (int i = 0; i < n; res[k++] = v[i++])
while (k > 1 && ccw(res[k - 2], res[k - 1], v[i]) <= 0) k--;
for (int i = n - 2, t = k; i >= 0; res[k++] = v[i--])
while (k > t && ccw(res[k - 2], res[k - 1], v[i]) <= 0) k--;
res.resize(k - 1);
return res;
}
void solve() {
INT(n, V);
vl p(n), v(n);
rep(i, n) {
scan(p[i], v[i]);
}
ld ok = 1e13, ng = 0;
auto f = [&](ld t) -> bool {
ld l = -1e18;
ld r = 1e18;
rep(i, n) {
if (p[i] > 0) {
chmin(r, p[i] - v[i] * t);
} else {
chmax(l, p[i] + v[i] * t);
}
}
return l - r >= 1e-15;
};
rep(_, 100) {
ld mid = (ok + ng) / 2;
if (f(mid)) ok = mid;
else ng = mid;
}
print(ok * V);
}
int main() {
int t;
cin >> t;
rep(i, t) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3676kb
input:
3 4 9 10 2 -7 2 -6 1 7 1 2 8 -1 7 1 6 2 3 -1000000000000 1 1000000000000 1
output:
38.250000000000002 1.230769230769231 3000000000000.000000238418579
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 716ms
memory: 3696kb
input:
10000 200 997007 405524182320 754760 686939601648 419804 687047488212 715566 1446157132 4594 -670522037 4673 763634629282 253755 424307411732 275041 1582708381 8473 -667425982 4622 -522841486 1427 702430907988 460271 1405423646 1060 1497754648 6227 883363410675 723547 56899800372 46435 -810216390 64...
output:
145405766328.349110051989555 16414958969.727281192317605 5202715639.835183900315315 321977234.156325868971180 45384199210.221683971583843 183885744.769230769248679 1708925225.230472358060069 89786664971.557942643761635 13924365606.287388795055449 412975327.555555555591127 965508404.512101492611691 4...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 1248ms
memory: 3988kb
input:
93 15435 968117 4196666 184 -5069875 255 -9782648 980 -1978138 176 9333323 764 -4323540 12 -8442049 319 -5371878 137 2881306 10 -4050629 133 -4659099 59 -5189169 320 -2256647 99 -3686648 37 1059255 33 -223142 20 8040933 408 8407764 705 694547 38 -7913614 746 -3573355 132 5919585 189 -3756662 94 -795...
output:
189662921.363636363734258 197971181.333333333343035 997533531.737629592476878 6439673170.665741784963757 993821598110.661077857017517 22727977326.402660988271236 34702455207.518504031002522 677770533.929817498719785 46631726883.969133235514164 5446481867.129032258410007 11336247450.272078595124185 4...
result:
ok 93 numbers
Test #4:
score: 0
Accepted
time: 985ms
memory: 9576kb
input:
5 400000 999972 172811492468 106699 171900177092 102097 194121748377 184014 190302947556 172722 183121572232 149212 196566712700 190884 171376795991 99358 522927044000 159597 -129031052077 34395 189422320931 170012 -275879974024 638546 408864707565 98475 -106703244806 368801 192128798630 178213 2915...
output:
519985220219.811770915985107 511413015796.766475379467010 424240880533.634020388126373 518849481155.503918796777725 1882496988186.444000005722046
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 1297ms
memory: 6800kb
input:
38 16668 999947 -3844782803 511 -210897941456 464872 618726004990 714384 -954596898686 225256 96675744 1148 -1515974078 11375 -206213840984 706184 306078847 3947 -474818331950 391451 -616022698917 561244 123378707 1540 -640636592655 406006 459201391325 908506 -733249583 5719 496163273 6238 619876911...
output:
89670748252.978608019649982 98630840901.507606960833073 29393530999.894327789545059 50801000770.955985423177481 39668001027.269331347197294 467846478226.411370843648911 30789914370.574311614036560 23151476830.905098434537649 51606123416.625827591866255 151713060001.662588924169540 100944679009.60928...
result:
ok 38 numbers