QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82231 | #5355. 多边形上天 | Recalling_Clouds | 0 | 2ms | 3904kb | C++14 | 4.2kb | 2023-02-27 11:35:09 | 2023-02-27 11:35:11 |
Judging History
answer
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)
#define x first
#define y second
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)
char _c; bool _f; template <class T> inline void IN (T & x) {
_f = 0, x = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f == 1) x = -x;
}
template <class T> inline void chkmin (T & x, T y) { if (x < y) x = y; }
template <class T> inline void chkmax (T & x, T y) { if (x < y) x = y; }
const int N = 2e3 + 5;
const double eps = 1e-6;
const double pi = acos ( -1 );
const double g = 9.8;
const double inf = 1e18;
inline bool equal (double a, double b) { return fabs (a - b) < eps; }
double v, w, r, theta;
inline double f1 (double t) { return cos (theta - t * w) * w * r + g * t; }
inline double f2 (double t) { return sin (theta - t * w) * w * r + v; }
inline double calc1 (double L) { return (sin (theta) - sin (theta - L * w)) * r + L * L / 2 * g; }
inline double calc2 (double L) { return (cos (theta - L * w) - cos (theta)) * r + L * v; }
int n;
pair <double, double> c;
inline double findtp (double L, double R) {
for (int t = 50; t; -- t) {
double len = (R - L) / 3, m1 = L + len, m2 = R - len;
(f1 (m1) < f1 (m2)) ? L = m1 : R = m2;
}
return L;
}
inline double doit (int a, int b, double & ret_a) {
if (! b) return ret_a = a, 0;
cout << "Yes" << endl ;
r = sqrt ((c.x - a) * (c.x - a) + (c.y - b) * (c.y - b));
theta = atan2 (b - c.y, a - c.x);
double st = theta / w, T = pi / w;
double tp = findtp (st - T / 2, st + T / 2);
double shift = (st + T / 2 - tp) * 2;
swap (tp, st);
if (st > 0) st -= floor (st / (2 * T)) * 2 * T;
if (st < 0) st += ceil ( ( - st) / (2 * T)) * 2 * T;
if (shift < eps) {
double L = 0, R = 2e5;
for (int t = 50; t; -- t) {
double mid = (L + R) / 2;
calc1 (mid) >= b ? R = mid : L = mid;
}
return ret_a = a + calc2 (L), L;
}
auto findrt = [&] (double L) -> double {
double R = L + shift;
if (f1 (R) >= 0) return inf;
for (int t = 30; t; -- t) {
double mid = (L + R) / 2;
f1 (mid) >= 0 ? L = mid : R = mid;
}
return L;
};
double lt = findrt (st - 2 * T), ret = 0, tot;
if (equal (lt, inf)) ret = 0;
else {
int L = 0, R = 2e5; // st + mid * 2 * T
if (lt >= 0) st -= 2 * T;
while (L <= R) {
int mid = (L + R) >> 1;
double lp = findrt (st + 2 * mid * T);
! equal (lp, inf) ? tot = mid, ret = lp, L = mid + 1 : R = mid - 1;
}
}
if (calc1 (ret) < b) {
double L = ret, R = 1e6;
for (int t = 50; t; -- t) {
double mid = (L + R) / 2;
calc1 (mid) >= b ? R = mid : L = mid;
}
ret = L;
} else {
int L = 0, R = tot, pt = -1;
double lm;
while (L <= R) {
int mid = (L + R) >> 1;
double lp = findrt (st + 2 * mid * T);
assert (! equal (lp, inf));
calc1 (lp) >= b ? lm = lp, pt = mid, R = mid - 1 : L = mid + 1;
}
assert ( ~ pt);
double A = st + 2 * (pt - 1) * T + shift, B = lm;
for (int t = 50; t; -- t) {
double mid = (A + B) / 2;
calc1 (mid) >= b ? B = mid : A = mid;
}
ret = A;
}
return ret_a = a + calc2 (ret), ret;
}
pair <int, int> p[N];
signed main () {
// freopen ( "nothing.in", "r", stdin ) ;
// freopen ( "nothing.out", "w", stdout ) ;
IN (n), IN (v), IN (w);
lep (i, 1, n) IN (p[i].x), IN (p[i].y);
lep (i, 1, n) c.x += p[i].x, c.y += p[i].y;
c.x /= n, c.y /= n;
double ans_t = inf, ans_a = 0;
lep (i, 1, n) {
double now_a, now_t = doit (p[i].x, p[i].y, now_a);
if (ans_t > now_t) swap (now_t, ans_t), swap (ans_a, now_a);
}
printf ("%.10lf\n", ans_a);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3904kb
input:
8 53 0 11 935 11 945 1 935 61 915 121 935 111 945 111 935 61 925
output:
Yes Yes Yes Yes Yes Yes Yes Yes 785.2497877469
result:
wrong output format Expected double, but "Yes" found
Subtask #2:
score: 0
Wrong Answer
Test #43:
score: 0
Wrong Answer
time: 2ms
memory: 3836kb
input:
8 811 14 11 911 11 921 1 911 61 891 121 911 111 921 111 911 61 901
output:
Yes Yes Yes Yes Yes Yes Yes Yes 10885.3995714496
result:
wrong output format Expected double, but "Yes" found
Subtask #3:
score: 0
Skipped
Dependency #1:
0%