QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497601 | #7670. Messenger | Max_s_xaM | AC ✓ | 83ms | 17368kb | C++14 | 4.8kb | 2024-07-29 14:43:30 | 2024-07-29 14:43:31 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 1e5 + 10;
const lf eps = 1e-8;
int n, m;
struct Point
{
lf x, y;
Point(lf _x = 0, lf _y = 0) : x(_x), y(_y) {}
Point operator + (const Point &u) const { return Point(x + u.x, y + u.y); }
Point operator - (const Point &u) const { return Point(x - u.x, y - u.y); }
Point operator * (const lf &u) const { return Point(x * u, y * u); }
Point operator / (const lf &u) const { return Point(x / u, y / u); }
};
inline lf sqr(const lf &x) { return x * x; }
inline lf dist(const Point &u) { return sqrt(sqr(u.x) + sqr(u.y)); }
inline lf dot(const Point &u, const Point &v) { return u.x * v.x + u.y * v.y; }
inline lf det(const Point &u, const Point &v) { return u.x * v.y - u.y * v.x; }
inline lf dist(const Point &x, const Point &y, const Point &u)
{
lf ans = min(dist(x - u), dist(y - u));
lf Dot = dot(u - x, y - x), d2 = dist(y - x);
if (Dot > 0 && Dot < d2 * d2) ans = min(ans, abs(det(y - x, u - x)) / d2);
return ans;
}
Point a[MAXN], b[MAXN], ia[MAXN], ib[MAXN];
Point c[MAXN], ic[MAXN];
lf da[MAXN], db[MAXN], dc[MAXN];
inline bool Check(lf x)
{
lf dt = 0; int tot = 0;
for (int i = 2; i <= m; i++)
{
if (dt + db[i] <= x) { dt += db[i]; continue; }
Point tmp = b[i - 1];
b[i - 1] = b[i - 1] + ib[i] * (x - dt), db[i] -= x - dt;
lf ta = 0, tb = 0;
c[tot = 1] = b[i - 1] - a[1];
for (int u = 2, v = i; u <= n && v <= m;)
if (tb + db[v] < ta + da[u])
{
tot++, ic[tot] = (u > n ? ib[v] : ib[v] - ia[u]), dc[tot] = tb + db[v] - max(tb, ta), c[tot] = c[tot - 1] + ic[tot] * dc[tot];
tb += db[v], v++;
}
else
{
tot++, ic[tot] = ib[v] - ia[u], dc[tot] = ta + da[u] - max(tb, ta), c[tot] = c[tot - 1] + ic[tot] * dc[tot];
ta += da[u], u++;
}
b[i - 1] = tmp, db[i] += x - dt;
break;
}
lf mn = 1e18;
for (int i = 2; i <= tot; i++) mn = min(mn, dist(c[i - 1], c[i], Point(0, 0)));
return mn < x || abs(mn - x) < eps;
}
int main()
{
// freopen("A.in", "r", stdin);
// freopen("A.out", "w", stdout);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n);
for (int i = 1; i <= n; i++) Read(a[i].x), Read(a[i].y);
for (int i = 2; i <= n; i++) ia[i] = a[i] - a[i - 1], da[i] = dist(ia[i]), ia[i] = ia[i] / da[i];
Read(m);
for (int i = 1; i <= m; i++) Read(b[i].x), Read(b[i].y);
lf sum = 0;
for (int i = 2; i <= m; i++) ib[i] = b[i] - b[i - 1], db[i] = dist(ib[i]), ib[i] = ib[i] / db[i], sum += db[i];
lf l = 0, r = sum, mid;
if (dist(b[m] - a[1]) - sum > eps) return cout << "impossible\n", 0;
while (r - l > eps)
{
mid = (l + r) / 2;
if (Check(mid)) r = mid;
else l = mid;
}
cout << fixed << setprecision(10) << l << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16212kb
input:
2 0 0 0 10 2 4 10 4 0
output:
3.9999999851
result:
ok correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 14212kb
input:
2 0 0 1 0 3 2 0 3 0 3 10
output:
4.9999999492
result:
ok correct
Test #3:
score: 0
Accepted
time: 2ms
memory: 15952kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 2ms
memory: 16216kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.0000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 1ms
memory: 13908kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 16072kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
29999.9999999864
result:
ok correct
Test #7:
score: 0
Accepted
time: 30ms
memory: 16616kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
3.3137084909
result:
ok correct
Test #8:
score: 0
Accepted
time: 2ms
memory: 14176kb
input:
2 0 0 30000 30000 2 0 30000 30000 0
output:
0.0000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 13968kb
input:
2 0 30000 0 0 2 1 0 0 0
output:
impossible
result:
ok correct
Test #10:
score: 0
Accepted
time: 2ms
memory: 16204kb
input:
2 0 1 0 0 2 30000 0 0 0
output:
14999.4999999944
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 16252kb
input:
2 0 0 15000 0 2 30000 0 15000 0
output:
0.0000000000
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 16200kb
input:
2 0 0 14999 0 2 30000 0 15000 0
output:
0.9999999907
result:
ok correct
Test #13:
score: 0
Accepted
time: 2ms
memory: 15956kb
input:
2 0 0 15000 0 2 30000 0 15001 0
output:
impossible
result:
ok correct
Test #14:
score: 0
Accepted
time: 1ms
memory: 14168kb
input:
2 0 15000 0 0 2 0 15000 0 30000
output:
0.0000000000
result:
ok correct
Test #15:
score: 0
Accepted
time: 2ms
memory: 16036kb
input:
2 0 14999 0 0 2 0 15000 0 30000
output:
impossible
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 16212kb
input:
2 0 0 0 30000 2 0 30000 0 0
output:
0.0000000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 15872kb
input:
2 0 30000 0 15000 2 0 15000 0 0
output:
impossible
result:
ok correct
Test #18:
score: 0
Accepted
time: 2ms
memory: 16008kb
input:
2 0 0 30000 30000 2 1 1 30000 30000
output:
impossible
result:
ok correct
Test #19:
score: 0
Accepted
time: 2ms
memory: 16216kb
input:
3 0 30000 15000 15000 0 0 3 30000 30000 15000 15000 30000 0
output:
0.0000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 2ms
memory: 16024kb
input:
2 0 0 0 1 3 30000 12426 30000 0 30000 30000
output:
impossible
result:
ok correct
Test #21:
score: 0
Accepted
time: 2ms
memory: 16256kb
input:
2 0 0 0 1 3 30000 12427 30000 0 30000 30000
output:
42424.9750140449
result:
ok correct
Test #22:
score: 0
Accepted
time: 2ms
memory: 16076kb
input:
4 0 30000 0 0 1 0 1 30000 4 30000 30000 30000 0 29999 0 29999 30000
output:
29998.9999999835
result:
ok correct
Test #23:
score: 0
Accepted
time: 19ms
memory: 17012kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
24142.1356236960
result:
ok correct
Test #24:
score: 0
Accepted
time: 35ms
memory: 16660kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
0.0000000000
result:
ok correct
Test #25:
score: 0
Accepted
time: 0ms
memory: 14164kb
input:
2 1 10 1 11 5 3 8 2 9 10 2 10 3 8 8
output:
1.4142135526
result:
ok correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 16216kb
input:
3 5 0 0 6 3 6 9 0 2 6 8 6 5 2 5 2 2 9 4 5 0 7 0 8 10
output:
1.9735690884
result:
ok correct
Test #27:
score: 0
Accepted
time: 2ms
memory: 16212kb
input:
8 4487 25213 15925 2555 11834 19731 24882 25400 29873 18185 20332 1130 20912 4660 2260 17776 7 1181 9778 6861 17903 1110 10850 8648 15950 13243 28850 23075 19352 14768 3464
output:
1452.5639082177
result:
ok correct
Test #28:
score: 0
Accepted
time: 1ms
memory: 14164kb
input:
8 5171 18241 3918 24817 6039 21929 19392 10844 5465 21271 18464 27403 5672 17224 17352 23648 8 13743 27832 6508 18183 93 25279 429 836 959 12741 1631 9065 17093 3127 6232 13449
output:
2339.7594870052
result:
ok correct
Test #29:
score: 0
Accepted
time: 0ms
memory: 16148kb
input:
306 7 0 1 4 9 7 8 6 3 7 2 5 9 2 5 8 6 2 4 9 5 10 10 10 10 3 5 1 3 8 9 6 7 4 8 9 6 4 10 6 6 8 6 3 10 1 0 7 8 5 2 4 1 10 10 10 4 10 10 3 1 10 7 5 1 2 10 8 1 2 3 7 6 1 6 8 5 3 2 8 7 2 0 6 2 5 7 3 0 9 2 9 7 9 8 7 7 1 1 5 7 8 9 3 9 9 0 2 6 7 7 5 5 9 8 4 7 7 8 6 8 0 0 3 0 10 3 6 6 3 1 7 8 5 3 9 7 9 2 7 3 ...
output:
0.0104863221
result:
ok correct
Test #30:
score: 0
Accepted
time: 0ms
memory: 16136kb
input:
283 10 2 8 8 2 9 5 3 6 7 6 2 3 3 10 9 10 4 9 7 3 3 9 6 3 10 3 0 6 10 1 7 8 3 0 5 3 8 10 0 9 4 7 3 3 6 3 2 10 5 6 2 3 6 8 3 10 8 2 6 3 4 2 10 2 8 7 10 0 5 5 0 6 6 2 6 8 9 10 3 6 3 3 9 8 10 0 7 0 10 0 8 1 8 7 1 0 1 7 10 0 1 1 9 8 3 5 10 9 6 7 5 9 8 5 8 8 6 3 5 9 1 9 8 6 1 6 0 0 0 8 1 1 10 2 0 5 0 3 1 ...
output:
0.0000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 2ms
memory: 16212kb
input:
99 246 227 1374 887 973 515 505 835 445 502 1524 361 589 217 728 637 988 74 1312 1493 192 485 150 951 903 1575 1358 1114 1564 829 262 1465 922 1078 679 912 561 947 1321 1165 948 1333 684 1456 243 1470 654 1373 894 897 149 1089 424 1162 213 293 845 555 508 441 999 1549 406 1020 16 1437 1335 112 174 1...
output:
18.2276316982
result:
ok correct
Test #32:
score: 0
Accepted
time: 2ms
memory: 14140kb
input:
625 189 776 733 112 1550 794 1148 1341 1236 403 944 153 1152 459 1271 831 203 358 912 1530 1196 1401 1014 758 378 736 130 182 555 20 1425 200 587 755 606 666 1423 1451 624 423 110 1403 26 424 1437 956 796 961 602 1586 331 373 850 800 1559 1508 536 1494 3 598 906 551 1162 1231 1348 106 592 1255 694 1...
output:
4.2479691555
result:
ok correct
Test #33:
score: 0
Accepted
time: 27ms
memory: 16460kb
input:
18051 32 15 3 3 11 2 2 30 32 14 15 25 34 16 10 12 13 31 14 16 15 35 16 24 18 35 24 4 11 22 21 7 24 12 6 32 25 24 23 2 21 2 3 15 13 9 32 6 26 25 21 30 20 23 22 5 16 11 26 15 15 27 25 32 31 28 5 19 15 20 1 25 3 24 30 5 29 11 19 11 26 9 9 29 7 1 15 3 35 32 18 4 13 25 23 25 32 11 10 19 25 0 28 6 5 35 13...
output:
0.0000000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 4ms
memory: 16228kb
input:
1587 1 16 34 21 28 4 16 22 35 8 1 15 20 18 10 15 23 16 1 23 16 14 15 22 3 34 4 35 34 22 32 16 19 20 7 10 13 20 16 8 11 26 24 35 25 26 19 14 21 4 10 11 3 30 15 11 21 12 11 0 25 17 1 0 33 31 2 26 14 21 19 1 0 32 19 19 3 5 30 29 5 18 21 29 28 8 34 2 25 22 14 5 32 7 1 21 13 23 8 35 31 26 9 2 2 24 25 23 ...
output:
0.0144415697
result:
ok correct
Test #35:
score: 0
Accepted
time: 79ms
memory: 16396kb
input:
50000 13 5 18 3 8 23 18 33 27 15 14 27 19 22 32 10 18 32 4 35 19 3 17 12 15 33 7 6 30 19 29 8 23 26 1 16 28 25 19 31 21 9 32 11 8 30 7 16 18 18 11 12 30 9 21 35 4 35 2 5 16 21 24 25 10 7 35 24 21 10 5 30 8 0 22 15 19 0 0 33 29 8 31 6 25 29 22 16 22 24 28 25 22 13 28 22 0 29 27 11 0 12 0 1 24 22 19 1...
output:
0.0000000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 83ms
memory: 17368kb
input:
50000 19 16 34 16 26 17 19 6 30 25 11 13 23 13 26 30 22 5 29 19 0 33 29 15 32 23 7 34 28 27 29 23 34 31 33 14 26 10 23 34 21 35 16 0 0 26 2 2 9 25 2 4 17 9 8 1 4 27 7 5 28 14 24 3 24 18 6 22 35 33 10 0 30 20 8 7 11 12 14 21 8 14 1 14 27 24 5 29 2 14 10 19 20 24 13 31 28 32 18 19 29 14 22 34 34 5 1 2...
output:
0.0000000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 0ms
memory: 16212kb
input:
4 5 5 5 2 4 5 7 6 50000 30 27 31 3 22 30 38 31 39 13 29 33 41 28 21 5 50 26 29 6 42 17 37 12 41 29 35 11 38 30 39 9 45 0 32 7 44 31 40 0 44 30 31 11 31 24 37 4 42 15 23 16 35 28 23 27 25 27 30 35 25 25 44 29 39 12 42 32 44 27 22 22 47 34 22 8 23 14 32 6 39 12 32 25 34 21 29 4 41 35 28 3 40 9 43 19 4...
output:
22.0379614556
result:
ok correct
Test #38:
score: 0
Accepted
time: 3ms
memory: 16204kb
input:
9 4 10 4 1 8 6 7 4 0 5 4 9 10 1 1 2 1 4 50000 48 7 40 0 42 29 22 13 46 19 35 21 40 19 54 15 55 26 36 21 44 16 31 30 20 5 37 31 51 9 45 31 26 15 54 30 51 1 54 2 54 22 31 2 52 19 43 17 26 31 41 20 38 20 39 19 44 34 52 1 33 29 33 11 38 28 30 29 43 20 52 8 36 29 26 20 45 23 39 13 53 5 47 10 52 3 54 7 40...
output:
20.2431066010
result:
ok correct
Test #39:
score: 0
Accepted
time: 2ms
memory: 14544kb
input:
2 4 19317 4 19318 37985 41 27 37 16 47 27 31 15 36 13 24 20 49 25 51 23 49 1 33 16 27 16 53 29 43 17 40 9 20 21 24 3 21 19 44 10 36 20 55 15 30 30 35 32 33 26 26 5 35 29 47 27 50 20 33 31 33 3 34 8 35 20 32 23 34 30 26 17 29 10 36 34 21 25 54 29 40 7 38 17 39 9 46 20 35 30 31 33 20 8 32 30 33 26 37 ...
output:
19289.9111706126
result:
ok correct
Test #40:
score: 0
Accepted
time: 3ms
memory: 16532kb
input:
6 3 25333 0 26159 6 15490 0 3432 4 8641 0 15506 41088 40 9 24 34 30 18 25 25 44 10 55 12 24 14 25 1 21 21 28 16 33 26 42 32 31 34 41 20 50 25 46 4 27 4 23 29 48 8 39 18 54 3 38 14 31 30 55 24 41 2 31 16 45 18 40 32 24 31 39 31 31 2 39 2 26 29 37 22 53 11 29 21 31 31 47 7 35 18 33 4 29 4 28 27 49 14 ...
output:
3406.3776154870
result:
ok correct
Test #41:
score: 0
Accepted
time: 0ms
memory: 14124kb
input:
4 7 18240 5 26771 3 24943 0 6628 7 20 1906 27 15217 20 15532 21 11073 27 334 23 16131 23 18367
output:
3222.0933119255
result:
ok correct
Test #42:
score: 0
Accepted
time: 2ms
memory: 16260kb
input:
4 8 15367 9 13231 10 3412 5 16414 10 26 15046 22 22728 24 22149 20 7329 27 26701 22 4714 27 4268 27 13007 28 27715 20 13727
output:
13.8607797362
result:
ok correct
Test #43:
score: 0
Accepted
time: 2ms
memory: 16164kb
input:
8 15009 21979 15010 23864 15007 5225 15003 4757 15009 16970 15007 15279 15003 4170 15007 27635 864 14373 15544 14972 14279 14674 14827 14729 14520 15657 15248 14953 14950 14346 14312 14476 14874 14476 15320 15384 15757 15017 15028 14567 14633 15610 14904 14751 15493 14357 14490 15321 14795 14676 151...
output:
17.8897882606
result:
ok correct
Test #44:
score: 0
Accepted
time: 1ms
memory: 14124kb
input:
6 15005 29323 15004 1778 15008 23555 15000 19170 15010 25875 15010 15988 154 15757 14866 15689 15407 14776 15688 15444 15769 15627 14793 14834 15211 14211 14961 14905 15228 14634 14324 15317 14937 15402 15641 15290 14306 14925 14641 14936 14261 15472 14801 15124 15800 14660 15632 15311 15017 15074 1...
output:
0.5386713568
result:
ok correct
Test #45:
score: 0
Accepted
time: 57ms
memory: 16896kb
input:
50000 30 20 9 34 25 8 24 4 35 34 6 29 9 15 25 7 4 1 26 21 8 5 31 33 11 28 16 23 29 10 1 30 15 23 14 4 19 22 7 27 11 9 20 12 11 23 30 16 29 24 15 3 5 19 3 2 27 18 25 23 9 2 2 22 18 25 34 35 31 0 35 10 26 28 33 13 28 0 30 33 18 28 0 19 7 25 31 23 26 6 31 33 4 33 5 12 25 15 2 18 22 19 19 5 13 24 13 6 1...
output:
42332.4154625816
result:
ok correct
Test #46:
score: 0
Accepted
time: 57ms
memory: 16336kb
input:
50000 31 13 2 25 10 20 1 31 9 33 9 28 0 32 30 20 18 15 30 34 10 20 6 1 34 14 26 21 19 18 20 27 11 34 12 18 29 32 8 26 34 10 12 16 15 35 33 30 23 19 26 7 32 12 6 10 27 33 14 11 23 8 6 7 15 10 1 32 16 17 31 26 8 8 11 23 10 34 6 15 7 29 2 16 6 35 17 14 5 8 28 2 6 12 32 7 30 27 6 23 15 27 20 30 17 2 31 ...
output:
42333.5614531233
result:
ok correct